首页 > 代码库 > AC日记——红色的幻想乡 洛谷 P3801
AC日记——红色的幻想乡 洛谷 P3801
红色的幻想乡
思路:
线段树+容斥原理;
代码:
#include <bits/stdc++.h>using namespace std;#define maxn 100005#define maxm maxn<<2#define ll long longclass TreeType { private: int L[maxm],R[maxm],mid[maxm],dis[maxm]; public: void build(int now,int l,int r) { L[now]=l,R[now]=r,dis[now]=0; if(l==r) return;mid[now]=l+r>>1; build(now<<1,l,mid[now]),build(now<<1|1,mid[now]+1,r); } void updata(int now,int to) { if(L[now]==R[now]) { dis[now]^=1; return; } if(to<=mid[now]) updata(now<<1,to); else updata(now<<1|1,to); dis[now]=dis[now<<1]+dis[now<<1|1]; } int query(int now,int l,int r) { if(L[now]>=l&&R[now]<=r) return dis[now]; int res=0; if(l<=mid[now]) res+=query(now<<1,l,r); if(r>mid[now]) res+=query(now<<1|1,l,r); return res; }};struct TreeType tree1,tree2;int n,m,q;inline void in(int &now){ char Cget=getchar();now=0; while(Cget>‘9‘||Cget<‘0‘) Cget=getchar(); while(Cget>=‘0‘&&Cget<=‘9‘) { now=now*10+Cget-‘0‘; Cget=getchar(); }}int main(){ in(n),in(m),in(q); tree1.build(1,1,n); tree2.build(1,1,m); int op,x1,y1,x2,y2; while(q--) { in(op),in(x1),in(y1); if(op==1) tree1.updata(1,x1),tree2.updata(1,y1); else { in(x2),in(y2); ll ans1=tree1.query(1,x1,x2),ans2=tree2.query(1,y1,y2); printf("%lld\n",ans1*(y2-y1+1)+ans2*(x2-x1+1)-ans1*ans2*2); } } return 0;}
AC日记——红色的幻想乡 洛谷 P3801
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。