洛谷3801 红色的幻想乡

传送门

这个题呢就是一个线段树+容斥原理的题，二维线段树我也不会这个题就是用两个线段树，一颗线段树就是求有多少列被修改过，另一颗线段树就是求有多少行被修改过，每次修改就是将他所在的行和列都修改一下，当询问的时候就询问x1到x2的和与y1到y2的和然后进行容斥原理，就可以得到答案了，以下是代码

#include
#include
#include
#include
using namespace std;struct node
{int l,r;int sum;
}t1[100001<<6],t2[100001<<6];void pushup1(int tr)
{t1[tr].sum=t1[tr<<1].sum+t1[tr<<1|1].sum;return;
}void build1(int l,int r,int tr)
{t1[tr].l=l;t1[tr].r=r;if(l==r){t1[tr].sum=0;return;}int mid=l+r>>1;build1(l,mid,tr<<1);build1(mid+1,r,tr<<1|1);pushup1(tr);return;
}void change1(int l,int r,int tr)
{if(t1[tr].l==t1[tr].r){t1[tr].sum^=1;return;}int mid=t1[tr].l+t1[tr].r>>1;if(l<=mid)change1(l,r,tr<<1);else change1(l,r,tr<<1|1);pushup1(tr);return;
} int query1(int l,int r,int tr)
{if(t1[tr].l>=l&&r>=t1[tr].r){return t1[tr].sum;}int ret=0,mid=t1[tr].l+t1[tr].r>>1;if(l<=mid)ret+=query1(l,r,tr<<1); if(mid<r)ret+=query1(l,r,tr<<1|1);return ret;
}void pushup2(int tr)
{t2[tr].sum=t2[tr<<1].sum+t2[tr<<1|1].sum;return;
}void build2(int l,int r,int tr)
{t2[tr].l=l;t2[tr].r=r;if(l==r){t2[tr].sum=0;return;}int mid=l+r>>1;build2(l,mid,tr<<1);build2(mid+1,r,tr<<1|1);pushup2(tr);return;
}void change2(int l,int r,int tr)
{if(t2[tr].l==t2[tr].r){t2[tr].sum^=1;return;}int mid=t2[tr].l+t2[tr].r>>1;if(l<=mid)change2(l,r,tr<<1);else change2(l,r,tr<<1|1);pushup2(tr);return;
} int query2(int l,int r,int tr)
{if(t2[tr].l>=l&&r>=t2[tr].r){return t2[tr].sum;}int ret=0,mid=t2[tr].l+t2[tr].r>>1;if(l<=mid)ret+=query2(l,r,tr<<1); if(mid<r)ret+=query2(l,r,tr<<1|1);return ret;
}
int main()
{long long n,m,q;cin>>n>>m>>q;build1(1,n,1);build2(1,m,1);for(int i=1;i<=q;i++){int zb;scanf("%d",&zb);if(zb==1){long long x,y;cin>>x>>y;//scanf("%d%d",&x,&y);change1(x,x,1);change2(y,y,1);}else{long long x1,x2,y1,y2;cin>>x1>>y1>>x2>>y2;//scanf("%d%d%d%d",&x1,&y1,&x2,&y2);long long a1,a2;a1=query1(x1,x2,1);a2=query2(y1,y2,1);cout<<a1*(long long)(y2-y1+1)+a2*(long long)(x2-x1+1)-(long long)(a1*a2<<1)<<endl;}}
}

这个线段树看起来很易懂，求过

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！