线段树相关

[TOC]

较高阶操作

维护较复杂信息

区间最大连续子段和

维护最大前缀和,后缀和和子段和。合并时注意跨越端点的情况即可。

按位拆分

对于 CF242E XOR on Segment 之类的问题,可以考虑将数二进制拆分,对于每一位都建一棵线段树方便处理。

扫描线

主要用途:求直角坐标系内矩形的周长并或面积并。

实际上,就是通过每一条扫描线对线段树进行区间修改和区间查询操作

求面积并

算法流程:

  1. 读入所有的矩形,水平边存入 line 数组,并标记为 1,上边标记为 -1,同时保存下所有的线段左右端点。
  2. line 数组按照高度从低到高排序,然后对所有的线段左右端点排序并离散化,记为 X[i]
  3. 从下往上依次扫描每个边,然后在线段树中进行操作统计第 i 到第 i+1 条扫描线中扫过的面积。

对于面积并,需要实现如下的线段树结构体:

struct SegTree
{
    int sum;//完全覆盖的线段个数
    ll len;//区间被覆盖的长度
}f[maxn<<2];

对于一个维护 [i,j] 的线段树节点,它实际上维护的是 (X_{i},X_{j+1}) 的线段被覆盖的情况。

对于一个覆盖了 (l,r) 的扫描线,需要对线段树进行如下处理:

void pushup(int i,int j,int k)
{
    if(f[k].sum)
        f[k].len=X[j+1]-X[i];//pushup,如果被覆盖完了
    else
        f[k].len=f[L].len+f[R].len;//合并左右子区间答案
    return;
}

void modify(int i,int j,int k,int l,int r,int opt)
{
    if(X[j+1]<=l || X[i]>=r)//如果该线段树维护的区间不被要求的区间覆盖就直接返回
        return;
    if(l<=X[i] && X[j+1]<=r)//如果完全包含
    {
        f[k].sum+=opt;//调整被覆盖的线段个数,+1和-1在结构体里解释的很清楚
        pushup(i,j,k);//pushup一波
        return;
    }
    modify(i,M,L,l,r,opt);
    modify(M+1,j,R,l,r,opt);
    pushup(i,j,k);
    return;
}

最终实现

struct ScanLine
{
    ll l,r,h;
    int mark;
    bool operator<(const ScanLine &b)const
    {
        return h<b.h;
    }
}line[maxn<<1];

ll X[maxn<<1];

struct SegTree
{
    int sum;//完全覆盖的个数
    ll len;//区间被覆盖的长度
}f[maxn<<2];

void build(int i,int j,int k)
{
    f[k].sum=f[k].len=0;
    if(i==j)
        return;
    build(i,M,L);
    build(M+1,j,R);
    return;
}

void pushup(int i,int j,int k)
{
    if(f[k].sum)
        f[k].len=X[j+1]-X[i];
    else
        f[k].len=f[L].len+f[R].len;
    return;
}

void modify(int i,int j,int k,int l,int r,int opt)
{
    if(X[j+1]<=l || X[i]>=r)
        return;
    if(l<=X[i] && X[j+1]<=r)
    {
        f[k].sum+=opt;
        pushup(i,j,k);
        return;
    }
    modify(i,M,L,l,r,opt);
    modify(M+1,j,R,l,r,opt);
    pushup(i,j,k);
    return;
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    {
        ll x1=read(),y1=read(),x2=read(),y2=read();
        X[(i<<1)-1]=x1,X[i<<1]=x2;
        line[(i<<1)-1]=(ScanLine){x1,x2,y1,1};
        line[i<<1]=(ScanLine){x1,x2,y2,-1};
    }
    n<<=1;
    sort(line+1,line+n+1);
    sort(X+1,X+n+1);
    int tot=unique(X+1,X+n+1)-X-1;
    build(1,tot-1,1);
    ll ans=0;
    for(int i=1;i<n;++i)
    {
        modify(1,tot-1,1,line[i].l,line[i].r,line[i].mark);
        ans+=f[1].len*(line[i+1].h-line[i].h);
    }
    printf("%lld\n",ans);
    return 0;
}

求周长并

和求面积并其实是差不多的,有两种方法,一种是扫描两次,一次横着一次竖着;一种是只扫描一次然后直接统计答案(前者更好理解一些)

不管是哪种方法,我们都先讨论下水平由下向上扫描的情形:不难发现每一条扫描线对水平边产生的贡献等于该条扫描线被覆盖的长度减去上一条扫描线被覆盖的长度的绝对值,手玩几次即可。

注意:同一水平线上的边先加边后删边,不然会出大问题:可以手玩如下样例:

input:

2
0 0 4 4
0 4 4 8

output:

24

加入的边按照 (h,l,r,mark) 排序后有 (0,0,4,1)(4,0,4,-1)(4,0,4,1)(8,0,4,-1),手玩即会发现如果先删边的话会出大问题,高度为 4 的边会被统计两次

如果要扫描第二遍的话,轻轻松松,重做一遍上述过程即可。

代码实现:

struct ScanLine
{
    ll l,r,h;
    int mark;
    bool operator<(const ScanLine &b)const
    {
        if(h==b.h)
            return mark>b.mark;//如果这里不特判会出问题,先加边后删边
        return h<b.h;
    }
}line[2][maxn<<1];

ll pos[2][maxn<<1];

struct SegTree
{
    int sum;
    ll len;
}f[maxn<<2][2];

void pushup(int i,int j,int k,int p)
{
    if(f[k][p].sum)
        f[k][p].len=pos[p][j+1]-pos[p][i];
    else
        f[k][p].len=f[L][p].len+f[R][p].len;
    return;
}

void modify(int i,int j,int k,int l,int r,int p,int opt)
{
    if(pos[p][i]>=r || pos[p][j+1]<=l)
        return;
    if(pos[p][i]>=l && pos[p][j+1]<=r)
    {
        f[k][p].sum+=opt;
        pushup(i,j,k,p);
        return;
    }
    modify(i,M,L,l,r,p,opt);
    modify(M+1,j,R,l,r,p,opt);
    pushup(i,j,k,p);
    return;
}

inline int abs(int x){...}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        line[0][(i<<1)-1]=(ScanLine){x1,x2,y1,1};
        line[0][(i<<1)]=(ScanLine){x1,x2,y2,-1};
        line[1][(i<<1)-1]=(ScanLine){y1,y2,x1,1};
        line[1][(i<<1)]=(ScanLine){y1,y2,x2,-1};
        pos[0][(i<<1)-1]=x1,pos[0][i<<1]=x2;
        pos[1][(i<<1)-1]=y1,pos[1][i<<1]=y2;
    }
    n<<=1;
    sort(line[0]+1,line[0]+n+1);
    sort(line[1]+1,line[1]+n+1);
    sort(pos[0]+1,pos[0]+n+1);
    sort(pos[1]+1,pos[1]+n+1);
    int tot[2];
    tot[0]=unique(pos[0]+1,pos[0]+n+1)-pos[0]-1;
    tot[1]=unique(pos[1]+1,pos[1]+n+1)-pos[1]-1;
    ll ans=0;
    for(int p=0;p<2;p++)//扫描两遍
    {
        ll lastans=0;
        for(int i=1;i<=n;i++)
        {
            modify(1,tot[p]-1,1,line[p][i].l,line[p][i].r,p,line[p][i].mark);
            ans+=abs(f[1][p].len-lastans);
            lastans=f[1][p].len;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

如果不扫描两遍,只自下而上扫描,那么为了统计竖直边的贡献,就需要统计扫描线覆盖了多少条线段,乘以二再乘以距离它上面的一条扫描线的高度差即可,手玩便知。

但是合并区间的时候就需要再记录两个标记,表示区间的左端点和右端点有没有被覆盖到,合并的时候需要注意如果左儿子的右端和右儿子的左端都被覆盖的话,总的线段条数就要减 1。

struct SegTree
{
    int sum;//完全覆盖的线段个数
    int num;//覆盖了的线段条数
    ll len;//区间被覆盖的长度
    bool lflag,rflag;//表示左/右端点是否被覆盖
}f[maxn<<2];

void pushup(int i,int j,int k)
{
    if(f[k].sum)
    {
        f[k].lflag=f[k].rflag=1;
        f[k].num=1;
        f[k].len=X[j+1]-X[i];//如果被完全覆盖
    }
    else
    {
        f[k].lflag=f[L].lflag;
        f[k].rflag=f[R].rflag;
        f[k].num=f[L].num+f[R].num;
        if(f[L].rflag && f[R].lflag)
            --f[k].num;
        f[k].len=f[L].len+f[R].len;
    }
    return;
}

剩下的就是主函数中的:

    int tot=unique(X+1,X+n+1)-X-1;
    ll ans=0,lastans=0;
    for(int i=1;i<n;++i)
    {
        modify(1,tot-1,1,line[i].l,line[i].r,line[i].mark);
        ans+=f[1].num*2*(line[i+1].h-line[i].h);//统计竖直边答案
        ans+=abs(f[1].len-lastans);//统计水平边答案
        lastans=f[1].len;//记录 lastans
    }
    ans+=line[n].r-line[n].l;//最顶上的边无论如何都会产生贡献
    printf("%lld\n",ans);

其实和下述写法是等效的:

        modify(1,tot-1,1,line[i].l,line[i].r,line[i].mark);
        if(i<n)ans+=f[1].num*2*(line[i+1].h-line[i].h);
        ans+=abs(f[1].len-lastans);
        lastans=f[1].len;

动态开点

线段树的堆式存储比较耗费空间,而且对于值域很大的情况下除了离线离散化无解,所以动态开店线段树应运而生。

动态开点其实也没多什么,就是对于一个编号为 k 的节点,它的左儿子不再是 2k,右儿子不再是 2k+1,而是我们自行记录的 l(k)r(k)

当我们需要这个节点的时候,我们就开这个节点即可。

存线段树的数组一般题目给多大空间开多大,或者随便估计一下即可

void modify(int i,int j,int &k,int x,int y,int opt)//注意这里节点编号 k 是引用传参,这样方便为父亲节点开点
{
    if(!k)
        k=++cnt;//如果这个点不存在,开这个点
    if(x<=i && y>=j){...}
    if(f[k].tag!=-1){...}
    if(x<=M)
        modify(i,M,L,x,y,opt);//L 是宏定义了的 f[k].lson
    if(y>M)
        modify(M+1,j,R,x,y,opt);
    f[k].val=f[L].val+f[R].val;//pushup
    return;
}

线段树优化建图

问题引入

经典题 CF786B Legacy。此题要求对 n 个点进行如下操作:

  • 连边 u\rightarrow v
  • 连边 u\rightarrow [l, r]
  • 连边 [l, r]\rightarrow v

边有正权。1\le n\leq 10^5

如果一个一个暴力连边,空间和时间肯定双重起飞,考虑优化

如何构建线段树

看到 [l, r],就想到使用数据结构来优化,此处我们可以使用线段树。考虑线段树的每个节点代表一个区间,然后给节点编号,每次处理加边操作就使对应编号的节点连边就行了。然而我们发现一棵线段树好像并不能解决问题,所以考虑两棵线段树,一棵处理出,一棵处理入。

出树

入树

然后线段树内连虚边,权为 0注意连边的方向,可以这样想:处理出的线段树中,[l,r] 肯定是可以出到 [l,mid][mid+1, r] 的,所以出线段树是向下连边,同理,入线段树是向上连边。同时在建树的过程中给节点编号,为了方便跑最短路,所有叶子节点的编号即为其代表图中节点的编号,然后至于维护区间的点使用一个 cnt 时间戳即可。建树的过程如下:

const int maxn = 1e5 + 5, INF = 0x3f3f3f3f3f3f3f3f;
int n, q, s, treeIn[maxn << 2], treeOut[maxn << 2], cnt;
bool vis[maxn * 10];

struct edge
{
    int to, nxt, dis;
} e[maxn * 30];

int cnte, head[maxn * 10], dis[maxn * 10];

void add(int u, int v, int w)
{
    e[++cnte].to = v;
    e[cnte].dis = w;
    e[cnte].nxt = head[u];
    head[u] = cnte;
    return;
}

void build(int i, int j, int k)
{
    if (i == j)
    {
        treeIn[k] = i, treeOut[k] = i;
        return;
    }
    build(i, M, ls);
    build(M + 1, j, rs);
    treeIn[k] = ++cnt, treeOut[k] = ++cnt;
    add(treeOut[ls], treeOut[k], 0);
    add(treeOut[rs], treeOut[k], 0);
    add(treeIn[k], treeIn[ls], 0);
    add(treeIn[k], treeIn[rs], 0);
    return;
}

如何加边

考虑 u\rightarrow[l,r] 的边该如何处理。其实相当简单,只需要在线段树上将 [l,r] 剖开,把 u 与代表对应区间的点连边即可,[l, r]\rightarrow u 同理。

然后呢?注意连边的先后就可以了

void update(int opt, int i, int j, int k, int l, int r, int u, int dist)
{
    if (i >= l && j <= r)
    {
        if (opt == 2)
            add(u, treeIn[k], dist);
        else add(treeOut[k], u, dist);
        return;
    }
    if (l <= M)
        update(opt, i, M, ls, l, r, u, dist);
    if (r > M)
        update(opt, M + 1, j, rs, l, r, u, dist);
}

总体实现

建完边之后直接 Dijsktra 就可以了,其实线段树优化建图的思想蛮简单的:就是使用线段树将区间合并成虚点以降低时空复杂度。当然实现需要注意:

  • 前向星存边的数组往死里开防止 RE,此题 20 倍足矣
  • 任何涉及到图的问题的数组都至少开 10 倍空间,不能忽略虚点的存在

剩下的也没什么需要注意的了,其实学习完线段树优化建图之后会发现它就是代码比较长,不熟练容易敲错,其他也没特别难。

此题开 long long

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#define R register
#define FOR(i, a, b) for (R signed i = a; i <= b; ++i)
#define ls (k << 1)
#define rs (ls | 1)
#define M ((i + j) >> 1)
#define int long long

inline int read()
{
    char c = getchar();
    int s = 0;
    bool x = 0;
    while (!isdigit(c))
        x = x | (c == '-'), c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

const int maxn = 1e5 + 5, INF = 0x3f3f3f3f3f3f3f3f;
int n, q, s, treeIn[maxn << 2], treeOut[maxn << 2], cnt;
bool vis[maxn * 10];

struct edge
{
    int to, nxt, dis;
} e[maxn * 30];

int cnte, head[maxn * 10], dis[maxn * 10];

void add(int u, int v, int w)
{
    e[++cnte].to = v;
    e[cnte].dis = w;
    e[cnte].nxt = head[u];
    head[u] = cnte;
    return;
}

void build(int i, int j, int k)
{
    if (i == j)
    {
        treeIn[k] = i, treeOut[k] = i;
        return;
    }
    build(i, M, ls);
    build(M + 1, j, rs);
    treeIn[k] = ++cnt, treeOut[k] = ++cnt;
    add(treeOut[ls], treeOut[k], 0);
    add(treeOut[rs], treeOut[k], 0);
    add(treeIn[k], treeIn[ls], 0);
    add(treeIn[k], treeIn[rs], 0);
    return;
}

void update(int opt, int i, int j, int k, int l, int r, int u, int dist)
{
    if (i >= l && j <= r)
    {
        if (opt == 2)
            add(u, treeIn[k], dist);
        else add(treeOut[k], u, dist);
        return;
    }
    if (l <= M)
        update(opt, i, M, ls, l, r, u, dist);
    if (r > M)
        update(opt, M + 1, j, rs, l, r, u, dist);
}

struct state
{
    int now, dist;
    state() {}
    state(int u, int w)
    {
        now = u, dist = w;
    }
    bool operator<(const state &b) const
    {
        return this->dist > b.dist;
    }
};

void dijkstra()
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    std::priority_queue<state> q;
    q.push(state(s, 0));
    while (!q.empty())
    {
        int now = q.top().now;
        q.pop();
        if (!vis[now])
        {
            vis[now] = 1;
            for (signed i = head[now]; i; i = e[i].nxt)
            {
                int &to = e[i].to, &w = e[i].dis;
                if (dis[to] > dis[now] + w)
                {
                    dis[to] = dis[now] + w;
                    q.push(state(to, dis[to]));
                }
            }
        }
    }
    return;
}

signed main()
{
    cnt = n = read(), q = read(), s = read();
    build(1, n, 1);
    R int opt, _u, _v, _w, _l, _r;
    while (q--)
    {
        opt = read();
        if (opt == 1)
        {
            _u = read(), _v = read(), _w = read();
            add(_u, _v, _w);
        }
        else
        {
            _u = read(), _l = read(), _r = read(), _w = read();
            update(opt, 1, n, 1, _l, _r, _u, _w);
        }
    }
    dijkstra();
    FOR(i, 1, n)
        printf("%lld ", dis[i] == INF ? -1 : dis[i]);
    return 0;
}

刷题记录

P2572 [SCOI2010]序列操作

题意

给定一 0/1 串,维护区间全变成 0/1、区间取反、区间查询 1 的个数以及区间查询最长连续 1 个数

思路

维护一个线段树结构体

struct seg
{
    int len, rev, tag, sum, pre[2], suf[2], ans[2];

    seg()
    {
        tag = -1;
        rev = 0;
        pre[1] = suf[1] = pre[0] = suf[0] = ans[1] = ans[0] = 0;
    }
} f[maxn << 2];

分别维护区间长度,区间取反标记,区间赋值标记(0/1 为全部,-1 为未修改),区间和,区间最长连续前缀 0/1,后缀 0/1,子段 0/1

合并区间信息时候

seg operator+(const seg &a, const seg &b)
{
    seg ret;
    ret.rev = 0;
    ret.sum = a.sum + b.sum;
    ret.len = a.len + b.len;
    ret.tag = -1; //-1 is none,1 is 1,0 is 0
    for (int k = 0; k <= 1; k++)
    {
        ret.pre[k] = a.pre[k];
        if (a.sum == a.len * k)
            ret.pre[k] = a.len + b.pre[k];
        ret.suf[k] = b.suf[k];
        if (b.sum == b.len * k)
            ret.suf[k] = b.len + a.suf[k];
        ret.ans[k] = max(a.ans[k], max(b.ans[k], a.suf[k] + b.pre[k]));
    }
    return ret;
}

即可

打标记时注意赋值操作会直接覆盖取反操作。

P1502 窗口的星星

题意

给定 n 个点,求 W\times H 的矩形最多能包含多少个点(边框不算)

思路

可以把每个点转化成以 (x,y) 为左下角顶点的 (W-1)\times(H-1),权值为 l 的矩形,然后求一波交的最大值。实际上就是维护一棵线段树,存储每个离散化的端点被矩形覆盖的权值大小,维护的是区间加和区间最大值查询。

实现

对于每一条下边,就对于区间 (l,r) 加上 l,对于上边减去即可,最后查询整个的最大值。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define L (k<<1)
#define R (L|1)
#define M ((i+j)>>1)

using std::sort;
using std::unique;

const int maxn=1e4+5;

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

inline int max(int a,int b)
{
    return a>b?a:b;
}

struct ScanLine
{
    int l,r,h;
    int mark;
    bool operator<(const ScanLine &b)const
    {
        if(h==b.h)
            return mark>b.mark;
        return h<b.h;
    }
}line[maxn<<1];

int X[maxn<<1];
int n,W,H;

struct SegTree
{
    int val,tag;
}f[maxn<<3];

void pushdown(int i,int j,int k)//下放懒标记
{
    f[L].tag+=f[k].tag,f[R].tag+=f[k].tag;
    f[L].val+=f[k].tag,f[R].val+=f[k].tag;
    f[k].tag=0;
    return;
}

void modify(int i,int j,int k,int l,int r,int d)
{
    if(X[j]<l || X[i]>r)
        return;
    if(X[i]>=l && X[j]<=r)//如果完全包含
    {
        f[k].val+=d;//对应的区间权值更新
        f[k].tag+=d;//懒标记更新
        return;
    }
    pushdown(i,j,k);
    modify(i,M,L,l,r,d);
    modify(M+1,j,R,l,r,d);
    f[k].val=max(f[L].val,f[R].val);//pushup
    return;
}

int main()
{
    int T=read();
    while(T--)
    {
        n=read(),W=read(),H=read();
        memset(line,0,sizeof line);
        memset(X,0,sizeof X);
        memset(f,0,sizeof f);
        for(int i=1;i<=n;i++)
        {
            int x=read(),y=read(),l=read();
            line[(i<<1)-1]=(ScanLine){x,x+W-1,y,l};
            line[i<<1]=(ScanLine){x,x+W-1,y+H-1,-l};
            X[(i<<1)-1]=x,X[i<<1]=x+W-1;
        }
        n<<=1;
        sort(line,line+n+1);
        sort(X,X+n+1);
        int tot=unique(X,X+n+1)-X-1;
        int ans=0;
        for(int i=1;i<n;i++)
        {
            modify(1,tot,1,line[i].l,line[i].r,line[i].mark);
            ans=max(ans,f[1].val);
        }
        printf("%d\n",ans);
    }
    return 0;
}

P5459 [BJOI2016]回转寿司

题意

给定 a_i,问有多少组 (l,r) 满足 L\le\sum_{i=l}^ra_i \le R(l,r) 对数。

思路

预处理前缀和 sum(i),变换式子后不难发现变为 sum(y)-R\le S_{x-1}\le sum(y)-L,使用权值线段树维护即可。

代码

#include <cstdio>
#include <cctype>
#define LS (f[k].lson)
#define RS (f[k].rson)
#define M ((i+j)>>1)

typedef long long ll;

inline ll read()
{
    char c = getchar();
    ll s = 0, x = 0;
    while (!isdigit(c))
    {
        if(c == '-')
            x = 1;
        c = getchar();
    }
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

const ll maxn=1e5+5,maxm=1e10;
ll sum[maxn],n,l,r,cnt;

struct SegTree
{
    int lson,rson;
    ll val;
    SegTree(){lson=rson=val=0;}
}f[(int)8e6+5];

void insert(ll i,ll j,int &k,ll x)
{
    if(!k)
        k=++cnt;
    if(i==j)
    {
        ++f[k].val;
        return;
    }
    if(x<=M)
        insert(i,M,LS,x);
    else
        insert(M+1,j,RS,x);
    f[k].val=f[LS].val+f[RS].val;
}

ll query(ll i,ll j,int &k,ll x,ll y)
{
    if(!k)
        k=++cnt;
    if(x<=i && y>=j)
        return f[k].val;
    ll ret=0;
    if(x<=M)
        ret+=query(i,M,LS,x,y);
    if(y>M)
        ret+=query(M+1,j,RS,x,y);
    return ret;
}

int main()
{
    n=read(),l=read(),r=read();
    ll ans=0;
    int root=1;
    insert(-maxm,maxm,root,0);
    for(int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+read();
        ans+=query(-maxm,maxm,root,sum[i]-r,sum[i]-l);
        insert(-maxm,maxm,root,sum[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

CF242E XOR on Segment

题意

查询区间和,区间异或上一个数,数据范围 10^5

思路

由于如果要支持区间异或的话普通的线段树无法胜任(异或没有结合律),所以考虑对于每一位都建一棵线段树,维护区间内该位 1 的个数。区间异或上一个数时可以一位一位考虑,是 1 就相当于反转区间并打标记。查询区间和的时候查询每一位的和乘上 2 的对应次方即可。

代码

#include <cstdio>
#include <cctype>
#define L (k << 1)
#define R (L | 1)
#define M ((i + j) >> 1)
#define reg register
#define il inline
#define FOR(i, a, b) for (reg int i = a; i <= b; ++i)
#define int long long

il int read()
{
    char c = getchar();
    int s = 0;
    bool x = 0;
    while (!isdigit(c))
        x = x | (c == '-'), c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return x ? -s : s;
}

const int maxn = 1e5 + 5;
int n, t[maxn << 2][32], tag[maxn << 2][32];

void pushup(int k)
{
    FOR(p, 0, 29)
        t[k][p] = t[L][p] + t[R][p];
    return;
}

void build(int i, int j, int k)
{
    if (i == j)
    {
        int tmp = read();
        for (reg int p = 0; tmp; tmp >>= 1, ++p)
            t[k][p] = (tmp & 1);
        return;
    }
    build(i, M, L);
    build(M + 1, j, R);
    pushup(k);
    return;
}

void pushdown(int i, int j, int k)
{
    FOR(p, 0, 29)
    {
        if (!tag[k][p])
            continue;
        t[L][p] = (M - i + 1) - t[L][p];
        t[R][p] = (j - M) - t[R][p];
        tag[L][p] ^= 1;
        tag[R][p] ^= 1;
        tag[k][p] = 0;
    }
    return;
}

int query(int i, int j, int k, int l, int r)
{
    if (l <= i && r >= j)
    {
        int ret = 0ll;
        FOR(p, 0, 29)
            ret += (t[k][p] << p);
        return ret;
    }
    int ret = 0ll;
    pushdown(i, j, k);
    if (l <= M)
        ret += query(i, M, L, l, r);
    if (r > M)
        ret += query(M + 1, j, R, l, r);
    return ret;
}

void modify(int i, int j, int k, int l, int r, int x)
{
    if (l <= i && r >= j)
    {
        FOR(p, 0, 29)
            for (reg int p = 0; x; x >>= 1, ++p)
                if (x & 1)
                {
                    tag[k][p] ^= 1;
                    t[k][p] = j - i + 1 - t[k][p];
                }
        return;
    }
    pushdown(i, j, k);
    if (l <= M)
        modify(i, M, L, l, r, x);
    if (r > M)
        modify(M + 1, j, R, l, r, x);
    pushup(k);
    return;
}

signed main()
{
    n = read();
    build(1, n, 1);
    int m = read();
    reg int opt, l, r, x;
    while (m--)
    {
        opt = read(), l = read(), r = read();
        if (opt == 1)
            printf("%lld\n", query(1, n, 1, l, r));
        else
            modify(1, n, 1, l, r, read());
    }
    return 0;
}
最后修改日期:2021年1月16日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。