codeforces #149 div 2
A 题，巨水，题意读懂就能A。

105.
就是所有线段的总长度不超过10^5。
晕了，这就表示最多是100000个点，可以用BFS来做。。。
#include <iostream>#include <cstdio>#include <algorithm>#include <string>#include <cmath>#include <cstring>#include <queue>#include <set>#include <vector>#include <stack>#include <map>#include <iomanip>#define PI acos(-1.0)#define Max 100000#define inf INT_MAX#define LL(x) (x<<1)#define RR(x) (x<<1|1)#define FOR(i,s,t) for(int i=(s);i<=(t);++i)#define ll long longusing namespace std;struct Seg_Tree{    int l,r,flag;    ll len;    ll digt[22];}tree[Max*4];int a[Max];void PushUp(int u){    for(int i=0;i<22;i++)    tree[u].digt[i]=tree[LL(u)].digt[i]+tree[RR(u)].digt[i];}void build(int l,int r,int u){    tree[u].l=l;    tree[u].r=r;    tree[u].len=r-l+1;    tree[u].flag=0;    if(l==r)    {        for(int i=0;i<22;i++)        if(1&(a[l]>>i))        tree[u].digt[i]=1;        return ;    }    int mid=l+r>>1;    build(l,mid,LL(u));    build(mid+1,r,RR(u));    PushUp(u);}void PushDown(int u){    if(tree[u].flag)    {        tree[LL(u)].flag^=tree[u].flag;        tree[RR(u)].flag^=tree[u].flag;        for(int i=0;i<22;i++)        if(1&(tree[u].flag>>i))        {            tree[LL(u)].digt[i]=tree[LL(u)].len-tree[LL(u)].digt[i];            tree[RR(u)].digt[i]=tree[RR(u)].len-tree[RR(u)].digt[i];        }    }    tree[u].flag=0;}void update(int l,int r,int u,int x){    if(l==tree[u].l&&tree[u].r==r)    {        tree[u].flag^=x;        for(int i=0;i<22;i++)        if(1&(x>>i))        tree[u].digt[i]=tree[u].len-tree[u].digt[i];        return ;    }    PushDown(u);    int mid=tree[u].l+tree[u].r>>1;    if(l>mid)    update(l,r,RR(u),x);    else if(r<=mid)    update(l,r,LL(u),x);    else    {        update(l,mid,LL(u),x);        update(mid+1,r,RR(u),x);    }    PushUp(u);}ll ans;void query(int l,int r,int u){    if(l==tree[u].l&&r==tree[u].r)    {        for(int i=0;i<22;i++)        ans+=tree[u].digt[i]*(1ll<<i);        return ;    }    PushDown(u);    int mid=tree[u].l+tree[u].r>>1;    if(l>mid)    query(l,r,RR(u));    else if (r<=mid)    query(l,r,LL(u));    else    {        query(l,mid,LL(u));        query(mid+1,r,RR(u));    }   // PushUp(u);}int main(){    int n;    cin>>n;    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);    int m;    cin>>m;    build(1,n,1);    while(m--)    {        int op;        scanf("%d",&op);        if(op==1)        {            int x,y;            scanf("%d%d",&x,&y);            ans=0;            query(x,y,1);            cout<<ans<<endl;        }        else        {            int x,y,z;            scanf("%d%d%d",&x,&y,&z);            update(x,y,1,z);        }    }    return 0;}