本文主要是介绍乱七八糟的树状数组和线段树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
//
// main.cpp
// 线段树rmq
//
// Created by liuzhe on 16/10/29.
// Copyright © 2016年 my_code. All rights reserved.
//
/*
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int max_,min_;
struct node
{
int l,r;
int max_,min_;
}segtree[800005];
int a[200005];
void build(int i,int l,int r)
{
segtree[i].l = l;
segtree[i].r = r;
if(l == r)
{
segtree[i].min_ = segtree[i].max_ = a[l];
return;
}
int mid = (l+r)/2;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
segtree[i].min_=min(segtree[i<<1].min_,segtree[i<<1|1].min_);
segtree[i].max_=max(segtree[i<<1].max_,segtree[i<<1|1].max_);
}
void query(int i,int l,int r)
{
if(segtree[i].max_<=max_&&segtree[i].min_>=min_)
return ;
if(segtree[i].l == l &&segtree[i].r == r)
{
max_=max(segtree[i].max_,max_);
min_=min(segtree[i].min_,min_);
return ;
}
int mid = (segtree[i].l+segtree[i].r)>>1;
if(r<=mid)
query(i<<2,l,r);
else
if(l>mid)
query(i<<1|1,l,r);
else
{
query(i<<1,l,mid);
query(i<<1|1,mid+1,r);
}
}
int main(int argc, const char * argv[]) {
// insert code here...
int n,q;
int l,r;
while(cin>>n>>q)
{
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int j=1;j<=q;j++)
{
scanf("%d%d",&l,&r);
max_=-99999999;
min_=99999999;
query(1,l,r);
printf("%d\n",max_-min_);
}
}
//std::cout << "Hello, World!\n";
return 0;
}*/
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
/*
#define MAXN 200005
#define INF 10000000
int nMax,nMin;//记录最大最小值
struct Node
{
int l,r;//区间的左右端点
int nMin,nMax;//区间的最小值和最大值
}segTree[MAXN*3];
int a[MAXN];
void Build(int i,int l,int r)//在结点i上建立区间为(l,r)
{
segTree[i].l=l;
segTree[i].r=r;
if(l==r)//叶子结点
{
segTree[i].nMin=segTree[i].nMax=a[l];
return;
}
int mid=(l+r)>>1;
Build(i<<1,l,mid);
Build(i<<1|1,mid+1,r);
segTree[i].nMin=min(segTree[i<<1].nMin,segTree[i<<1|1].nMin);
segTree[i].nMax=max(segTree[i<<1].nMax,segTree[i<<1|1].nMax);
}
void Query(int i,int l,int r)//查询结点i上l-r的最大值和最小值
{
if(segTree[i].nMax<=nMax&&segTree[i].nMin>=nMin) return;
if(segTree[i].l==l&&segTree[i].r==r)
{
nMax=max(segTree[i].nMax,nMax);
nMin=min(segTree[i].nMin,nMin);
return;
}
int mid=(segTree[i].l+segTree[i].r)>>1;
if(r<=mid) Query(i<<1,l,r);
else if(l>mid) Query(i<<1|1,l,r);
else
{
Query(i<<1,l,mid);
Query(i<<1|1,mid+1,r);
}
}
int main()
{
int n,q;
int l,r;
int i;
while(scanf("%d%d",&n,&q)!=EOF)
{
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
Build(1,1,n);
for(i=1;i<=q;i++)
{
scanf("%d%d",&l,&r);
nMax=-INF;nMin=INF;
Query(1,l,r);
printf("%d\n",nMax-nMin);
}
}
return 0;
}
*/
//模板
/*
int lowbit(int x)
{
return x & (-x);
}
//modify函数是将第x位的值增加add
void modify(int x,int add)//一维
{
while(x<=MAXN)
{
a[x]+=add;
x+=lowbit(x);
}
}
int get_sum(int x)
{
int ret=0;
while(x!=0)
{
ret+=a[x];
x-=lowbit(x);
}
return ret;
}
void modify(int x,int y,int data)//二维
{
for(int i=x;i<MAXN;i+=lowbit(i))
for(int j=y;j<MAXN;j+=lowbit(j))
a[i][j]+=data;
}
//get_sum是询问1到当前x的区间
int get_sum(int x,int y)
{
int res=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
res+=a[i][j];
return res;
}
*/
/*
int n,tree[100005];
int lowbit(int i)
{
return i & (-i);
}
void update(int i,int x)
{
for(;i<=n;i+=lowbit(i))
tree[i]+=x;
//while(i<=n)
//{
// tree[i]+=x;
//i+=lowbit(i);
//}
}
int query(int n)
{
int sum=0;
for(;n>0;n-=lowbit(n))
sum+=tree[n];
return sum;
}
int main()
{
int t;
cin>>t;
for(int cas=1;cas<=t;cas++)
{
memset(tree,0,sizeof(tree));
cout<<"Case "<<cas<<':'<<endl;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
update(i,x);
}
char s[10];
while(scanf("%s",s)!=-1&&strcmp(s,"End"))
{
int a,b;
scanf("%d%d",&a,&b);
if(s[0]=='Q')
printf("%d\n",query(b)-query(a-1));
else
if(s[0]=='S')
update(a,-b);
else
update(a,b);
}
}
return 0;
}
*/
/*
//int tree[1005];
long long n,m,k,t;
long long tr[1000005];
struct node
{
long long s,e;
}tree[1000005];
long long cmp(node a,node b)
{
if(a.s!=b.s)
return (a.s)<(b.s);
else
return (a.e)<(b.e);
}
long long lowbit(long long i)
{
return i&(-i);
}
void update(long long i,long long x)
{
for(;i<=k;i+=lowbit(i))
tr[i]+=x;
}
long long query(long long n)
{
long long sum=0;
for(;n>0;n-=lowbit(n))
sum+=tr[n];
return sum;
}
int main()
{
cin>>t;
for(long long cas=1;cas<=t;cas++)
{
long long ans = 0;
memset(tree,0,sizeof(tree));
memset(tr,0,sizeof(tr));
cin>>n>>m>>k;
for(long long i=1;i<=k;i++)
scanf("%lld%lld",&tree[i].e,&tree[i].s);
sort(tree+1,tree+1+k,cmp);
//for(int i=1;i<=k;i++)
// cout<<tree[i].s<<' '<<tree[i].e<<endl;
// tr[i]=tree[i].e;
for(long long i=1;i<=k;i++)
{
long long a=tree[i].e;
update(a,1);
ans+=(query(m)-query(a));
}
printf("Test case %lld: ",cas);
printf("%lld\n",ans);
}
return 0;
}
*/
/*
#define lowbit(x) (x&-x)
const int N=1000005;
struct node
{
int l,r,id;
} a[N];
int n,c[N],x,y;
int cmp(node a,node b)
{
if(a.l!=b.l)
return a.l<b.l;
return a.r<b.r;
}
int sum(int x)
{
int ret = 0;
while(x>0)
{
ret+=c[x];
x-=lowbit(x);
}
return ret;
}
void add(int x,int d)
{
while(x<=y)
{
c[x]+=d;
x+=lowbit(x);
}
}
long long ans;
int main()
{
int i,j,k,l,r,t,cas = 1;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d",&x,&y,&n);
memset(c,0,sizeof(c));
for(i = 1; i<=n; i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
}
sort(a+1,a+1+n,cmp);
ans = 0;
for(i = 1; i<=n; i++)
{
add(a[i].r,1);
ans+=sum(y)-sum(a[i].r);
}
printf("Test case %d: %lld\n",cas++,ans);
}
return 0;
}
*/
/*
//int num[100005];
int a,b,x;
struct Tree
{
int l,r,num,lazy;
}
tree[400005];
void build(int root,int l,int r)
{
tree[root].l=l;
tree[root].r=r;
tree[root].num = r-l+1;
tree[root].lazy=1;
if(l==r)
{
//tree[root].sum=num[l];
return;
}
int mid = (l+r)/2;
build(root<<1,l,mid);
build(root<<1|1,mid+1,r);
//tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum;
}
void update(int root,int x,int y,int val)
{
int ll,rr;
ll=tree[root].l;
rr=tree[root].r;
if(ll==x&&rr==y)
{
tree[root].lazy=1;
tree[root].num=(rr-ll+1)*val;
return ;
}
int mid = (tree[root].r+tree[root].l)>>1;
if(tree[root].lazy)
{
tree[root].lazy=0;
update(root<<1,ll,mid,tree[root].num*(rr-ll+1));
update(root<<1|1,mid,rr,tree[root].num*(rr-ll+1));
}
if(x<=mid)
update(root<<1,x,min(mid,y),val);
if(y>=mid)
update(root<<1|1,max(mid+1,x),y,val);
tree[root].num=tree[root<<1].num+tree[root<<1|1].num;
//tree[root].sum = tree[root<<1].sum+tree[root<<1|1].sum;
}
int query(int root)
{
//if(l<=tree[root].l&&r>=tree[root].r)
// return tree[root].sum;
//int mid = (tree[root].l+tree[root].r)>>1,ret=0;
//if(l<=mid)
// ret+=query(root<<1,l,r);
//if(r>mid)
// ret+=query(root<<1|1,l,r);
//return ret;
if(tree[root].lazy)
return tree[root].num;
return query(root<<1)+query(root<<1|1);
}
int main()
{
int ca,cas=1;
int n,t;
cin>>ca;
while(ca--)
{
cin>>n>>t;
//for(int i=1;i<=n;i++)
//memset(num,1,sizeof(num));
build(1,1,n);
printf("Case %d: The total value of the hook is ",cas++);
while(t--)
{
scanf("%d%d%d",&a,&b,&x);
//for(int j=a;j<=b;j++)
update(1,a,b,x);
//update(1,b,x);
//update(1,(a-1),-x);
}
printf("%d\n",query(1));
}
return 0;
}
*/
/*
typedef struct
{
int l,r,num,lazy;
}Tree;
Tree tree[500005];
void Build(int t,int l,int r)
{
int mid;
tree[t].l=l;
tree[t].r=r;
tree[t].num=r-l+1;
tree[t].lazy=1;
if (l==r) return;
mid=(l+r)/2;
Build(2*t+1,l,mid);
Build(2*t+2,mid+1,r);
}
void Add(int t,int x,int y,int c)
{
int mid,l,r;
l=tree[t].l;
r=tree[t].r;
if (l==x && r==y)
{
tree[t].lazy=1;
tree[t].num=(r-l+1)*c;
return;
}
mid=(l+r)/2;
if (tree[t].lazy==1)
{
tree[t].lazy=0;
Add(2*t+1,l,mid,tree[t].num/(r-l+1));
Add(2*t+2,mid+1,r,tree[t].num/(r-l+1));
}
if (x<=mid) Add(2*t+1,x,min(mid,y),c);
if (y>mid) Add(2*t+2,max(mid+1,x),y,c);
tree[t].num=tree[2*t+1].num+tree[2*t+2].num;
}
int Find(int t)
{
if (tree[t].lazy==1) return tree[t].num;
return Find(2*t+1)+Find(2*t+2);
}
int main()
{
int i,j,n,T,m,x,y,c,cnt=1;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
Build(0,0,n-1);
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d",&x,&y,&c);
Add(0,x-1,y-1,c);
}
printf("Case %d: The total value of the hook is %d.\n",cnt++,Find(0));
}
return 0;
}
1
10
2
1 5 2
5 9 3
*/
/*
int n,tree[500005];
int an[500005];
struct node
{
int v,order;
}in[500005];
int lowbit(int i)
{
return i & (-i);
}
void update(int i,int x)
{
for(;i<=n;i+=lowbit(i))
tree[i]+=x;
}
int query(int n)
{
int sum=0;
for(;n>0;n-=lowbit(n))
sum+=tree[n];
return sum;
}
bool cmp(node a,node b)
{
return a.v<b.v;
}
int main()
{
while(cin>>n&&n)
{
long long ans=0;
memset(tree,0,sizeof(tree));
for(int i=1;i<=n;i++)
{
scanf("%d",&in[i].v);
in[i].order=i;
}
sort(in+1,in+1+n,cmp);
for(int i=1;i<=n;i++)
an[in[i].order]=i;
for(int i=1;i<=n;i++)
{
update(an[i],1);
ans+=i-query(an[i]);
}
printf("%lld\n",ans);
}
return 0;
}
*/
/*
说明：
1. rt、L、R都是从1开始计数；
2. 线段树的空间应当是原数组的四倍；(最小应该为，向上取到最近的二的次幂，再乘以2)
3. 每次调用build，query和update时，L和R应该是整个区间（1-N），一般写成query(1,1,N)。
*/
/*
#define lson rt<<1,L,M
#define rson rt<<1|1,M+1,R
#define maxn 2000000 + 10
int sumv[maxn<<2]; //树上结点
int lazy[maxn<<2];//仅当区间更新时使用，点更新不需要
void pushUp(int rt) {
sumv[rt] = sumv[rt<<1] | sumv[rt<<1|1];
}
//区间更新时才需要使用pushDown
void pushDown(int rt) { //len在主函数里一般为 r - l +１
lazy[rt<<1] = lazy[rt<<1|1] = lazy[rt]; // lazy标记向两个儿子传递
sumv[rt<<1] = lazy[rt]; // 更新左儿子sumv
sumv[rt<<1|1] = lazy[rt]; // 更新右儿子sumv
lazy[rt] = 0; // 向下传递完后清空当前结点lazy标记
}
void build(int rt, int L, int R) {
int M = (L+R) >> 1;
if (L == R) {
sumv[rt] = 2; //始化线段树。
} else {
build(lson);
build(rson);
pushUp(rt);
}
}
//区间更新
void update(int tl, int tr, int v, int rt, int L, int R){
int M = (L+R)>>1;
if (tl<=L && R<=tr) {
lazy[rt] = v;
sumv[rt] = v;
} else {
if (lazy[rt]) pushDown(rt, R-L+1);
if (tl <= M) update(tl, tr, v, lson);
if (tr >= M+1) update(tl, tr, v, rson);
pushUp(rt);
}
}
int query(int tl, int tr, int rt, int L, int R) {
int M = (L+R) >> 1;
int ret = 0;
if (lazy[rt]) pushDown(rt, R-L+1);
if (tl<=L && R<=tr) return sumv[rt]; // 查询区间涵盖了整个区间
if (tl <= M) ret |= query(tl, tr, lson); // 查询区间在左边有分布
if (M < tr) ret |= query(tl, tr, rson); // 查询区间在右边有分布
return ret;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m) != EOF)
{
memset(lazy,0,sizeof(lazy));
if (n == 0 && m == 0) break;
build(1,1,n);
while(m--)
{
char ch;
scanf("%*c%c",&ch);
if (ch == 'P')
{
int x,y,value;
scanf("%d%d%d",&x,&y,&value);
update(x,y,1 << (value - 1),1,1,n);
}
else
{
int x,y;
scanf("%d%d",&x,&y);
int ans = query(x,y,1,1,n);
int first = 1;
for (int i = 1; i <= 32; i++)
{
if (ans & 1)
{
if (first)
{
first = 0;
printf("%d",i);
}
else
{
printf(" %d",i);
}
}
ans >>= 1;
}
printf("\n");
}
}
}
return 0;
}
*/
/*
int level[40005],sum[40005];
//sum[i]中装的是x不大于i的点的个数
int lowbit(int i)
{
return i&(-i);
}
int getsum(int i)
{
int s=0;
for(;i>0;i-=lowbit(i))
s+=sum[i];
return s;
}
void update(int x)
{
while(x<40005)
{
sum[x]++;
x+=lowbit(x);
}
}
int main()
{
int n,x,y;
while(scanf("%d",&n)!=-1)
{
memset(sum,0,sizeof(sum));
memset(level,0,sizeof(level));
for(int i=0;i<n;i++)
{
scanf("%d%d",&x,&y);
level[getsum(x+1)]++;
update(x+1);
}
for(int i=0;i<n;++i)
printf("%d\n",level[i]);
}
return 0;
}
*/
/*
const int N = 1000010;
struct tree{
int lp,rp,minvalue,maxvalue;
int getmid(){
return (lp + rp) / 2;
}
}tt[N * 4];
struct ans{
int minans,maxans;
}aa[N];
int num[N];
void built_tree(int lp,int rp,int pos){
tt[pos].lp = lp;
tt[pos].rp = rp;
int mid = tt[pos].getmid();
if(lp == rp){
tt[pos].minvalue = tt[pos].maxvalue = num[lp];
return;
}
built_tree(lp,mid,pos*2);
built_tree(mid+1,rp,pos*2+1);
tt[pos].minvalue = min(tt[pos*2].minvalue,tt[pos*2+1].minvalue);
tt[pos].maxvalue = max(tt[pos*2].maxvalue,tt[pos*2+1].maxvalue);
}
int query(int lp,int rp,int pos ,int id){
if(tt[pos].lp == lp && tt[pos].rp == rp){
if(id == 0)
return tt[pos].minvalue;
else
return tt[pos].maxvalue;
}
int mid = tt[pos].getmid();
if(mid >= rp)
return query(lp,rp,pos*2,id);
else if(mid < lp)
return query(lp,rp,pos*2+1,id);
else{
if(id == 0)
return min(query(lp,mid,pos*2,id),query(mid+1,rp,pos*2+1,id));
else
return max(query(lp,mid,pos*2,id),query(mid+1,rp,pos*2+1,id));
}
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m) != EOF){
for(int i = 1; i <= n; ++i)
scanf("%d",&num[i]);
built_tree(1,n,1);
for(int i = 1; i <= n - m + 1; ++i){
int j = i + m - 1;
aa[i].minans = query(i,j,1,0);
aa[i].maxans = query(i,j,1,1);
}
for(int i = 1; i < n - m + 1; ++i)
printf("%d ",aa[i].minans);
printf("%d\n",aa[n-m+1].minans);
for(int i = 1; i < n - m + 1; ++i)
printf("%d ",aa[i].maxans);
printf("%d\n",aa[n-m+1].maxans);
}
return 0;
}
*/
/*
const int N=1000005;
struct Tree{
int l,r,minvalue,maxvalue;
};
Tree tree[4*N];
struct Ans{
int minans,maxans;
};
Ans ans[N];
int num[N];
void buildtree(int root,int l,int r)
{
tree[root].l=l;
tree[root].r=r;
int mid=(tree[root].l+tree[root].r)>>1;
if(l==r)
{
tree[root].minvalue = tree[root].maxvalue = num[l];
return ;
}
buildtree(root<<1,l,mid);
buildtree(root<<1|1,mid+1,r);
tree[root].maxvalue=max(tree[root<<1].maxvalue,tree[root<<1|1].maxvalue);
tree[root].minvalue=min(tree[root<<1].minvalue,tree[root<<1|1].minvalue);
}
int query(int l,int r,int root,int flag)
{
if(tree[root].l==l&&r==tree[root].r)
{
if(flag)
return tree[root].maxvalue;
else
return tree[root].minvalue;
}
int mid = (tree[root].l+tree[root].r)>>1;
if(r<=mid)
{
return query(l,r,root<<1,flag);
}
else
if(l>mid)
{
return query(l,r,root<<1|1,flag);
}
else
if(flag)
return max(query(l,mid,root<<1,flag),query(mid+1,r,root<<1|1,flag));
else
return min(query(l,mid,root<<1,flag),query(mid+1,r,root<<1|1,flag));
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=-1)
{
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
buildtree(1,1,n);
for(int i=1;i<=n-m+1;i++)
{
ans[i].maxans=query(i,i+m-1,1,1);//1代表大
ans[i].minans=query(i,i+m-1,1,0);//0代表小
}
for(int i=1;i<=n-m+1;++i)
printf("%d ",ans[i].minans);
printf("\n");
for(int i=1;i<=n-m+1;++i)
printf("%d ",ans[i].maxans);
printf("\n");
}
return 0;
}
*/
/*
const int maxn=1000011;
struct Node{
int l,r,root,min,max;
}tree[maxn*5];
int minl[maxn],maxl[maxn],a[maxn],k,len;
void build(int l,int r,int root){
tree[root].l=l;
tree[root].r=r;
if(l==r){
tree[root].min=tree[root].max=a[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,root*2);
build(mid+1,r,root*2+1);
tree[root].min=min(tree[root*2].min,tree[root*2+1].min);
tree[root].max=max(tree[root*2].max,tree[root*2+1].max);
}
bool init(){
if(scanf("%d",&k)==EOF)return false;
scanf("%d",&len);
for(int i=1;i<=k;i++)scanf("%d",&a[i]);
build(1,k,1);
return true;
}
void query(int l,int r,int &min,int &max,int root){
if(tree[root].l==l&&tree[root].r==r){
min=tree[root].min;
max=tree[root].max;
return;
}
int mid=(tree[root].l+tree[root].r)>>1;
if(mid>=r)query(l,r,min,max,root*2);
else if(mid<l)query(l,r,min,max,root*2+1);
else{
int max2,min2;
query(l,mid,min,max,root*2);
query(mid+1,r,min2,max2,root*2+1);
min=min<min2?min:min2;
max=max>max2?max:max2;
}
}
void work(){
int ans1,ans2,i;
for(i=1;i<=k-len+1;i++){
query(i,i+len-1,ans2,ans1,1);
minl[i]=ans2;
maxl[i]=ans1;
}
}
void print(){
int i;
for(i=1;i<=k-len+1;i++)printf("%d ",minl[i]);
cout<<endl;
for(i=1;i<=k-len+1;i++)printf("%d ",maxl[i]);
cout<<endl;
}
int main(){
while(init()){
work();
print();
}
return 0;
}
*/
/*
int n,cnt;
const int maxn = 100010;
struct node
{
int l,r,n;//n统计颜色
};
node a[maxn<<2];
struct qujian
{
int point;//point纪录去见的边
int num;//num记录位置
};
qujian s[maxn<<2];
int Map[maxn<<1][2];
int ans;
int flag[maxn<<1];
int cmp(qujian a,qujian b)
{
return a.point<b.point;
}
void init(int l,int r,int i)//建树
{
a[i].l=l;
a[i].r=r;
a[i].n=0;
if(l!=r)
{
int mid = (l+r)>>1;
init(l,mid,i<<1);
init(mid+1,r,i<<1|1);
}
}
void update(int i,int l,int r,int m)
{
if(a[i].l==l&&a[i].r==r)
{
a[i].n=m;
return ;
}
int mid=(a[i].l+a[i].r)>>1;
if(a[i].n>0)//重点：如果这个区间访问过了，而且这个区间没有颜色
//就要将这个区间的颜色更新到其左右孩子的节点，并且要将个
//区间的颜色清空，才算是覆盖。
{
a[i<<1].n=a[i<<1|1].n=a[i].n;
a[i].n=0;
}
if(r<=a[i*2].l)
update(i<<1,l,r,m);
else
if(l>a[i<<1|1].l)
update(i<<1|1,l,r,m);
else
{
update(i<<1,l,mid,m);
update(i<<1|1,mid+1,r,m);
}
}
void query(int i)
{
if(a[i].n)
{
if(!flag[a[i].n])
{
ans++;
flag[a[i].n]=1;
}
return ;
}
query(i<<1);
query(i<<1|1);
return ;
}
int main()
{
int t;
cin>>t;
while(t--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)//离散化
{
scanf("%d%d",&Map[i][0],&Map[i][1]);
s[i<<1].point = Map[i][0];
s[i<<1|1].point = Map[i][1];
s[i<<1].num=-i-1;
s[i<<1|1].num=i+1;
}
sort(s,s+n*2,cmp);
int tmp = s[0].point;
cnt = 1;
for(int i=0;i<n<<1;i++)
{
if(tmp!=s[i].point)//和前面的不同，迭代加一
{
cnt++;
tmp=s[i].point;
}
if(s[i].num>=0)
Map[s[i].num-1][1] = cnt;
else
Map[-s[i].num-1][0]=cnt;
}
init(1,cnt,1);
for(int i=0;i<n;i++)
{
update(1,Map[i][0],Map[i][1],i+1);
}
memset(flag,0,sizeof(flag));
ans=0;
query(1);
cout<<ans<<endl;
}
return 0;
}
*/
int n,m;
int c[1005][1005];
int lowbit(int i)
{
return i&(-1);
}
int sum(int i,int j)
{
int ans=0;
for(;i>0;i-=lowbit(i))
for(;j>0;j-=lowbit(j))
ans += c[i][j];
return ans;
}
void query(int i,int j)
{
for(;i<=n;i+=lowbit(i))
for(;j<=n;j+=lowbit(j));
c[i][j]++;
}
int main()
{
int X;
cin>>X;
while(X--)
{
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
while(m--)
{
getchar();
char s;
scanf("%c",&s);
if(s=='C')
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
query(x2+1,y2+1);
query(x1,y1);
query(x2+1,y1);
query(x1,y2+1);
}
else
{
int x1,y1;
scanf("%d%d",&x1,&y1);
x1++;
y1++;
printf("%d\n",sum(x1,y1)%2);
}
}
printf("\n");
}
return 0;
}
这篇关于乱七八糟的树状数组和线段树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
