首页 > 代码库 > [luogu P3801] 红色的幻想乡 [线段树][树状数组]
[luogu P3801] 红色的幻想乡 [线段树][树状数组]
题目背景
蕾米莉亚的红雾异变失败后，很不甘心。
题目描述
经过上次失败后，蕾米莉亚决定再次发动红雾异变，但为了防止被灵梦退治，她决定将红雾以奇怪的阵势释放。
我们将幻想乡看做是一个n*m的方格地区，一开始没有任何一个地区被红雾遮盖。蕾米莉亚每次站在某一个地区上，向东南西北四个方向各发出一条无限长的红雾，可以影响到整行/整列，但不会影响到她所站的那个地区。如果两阵红雾碰撞，则会因为密度过大而沉降消失。灵梦察觉到了这次异变，决定去解决它。但在解决之前，灵梦想要了解一片范围红雾的密度。可以简述为两种操作:
1 x y 蕾米莉亚站在坐标(x,y)的位置向四个方向释放无限长的红雾。
2 x1 y1 x2 y2 询问左上点为(x1,y1)，右下点为(x2,y2)的矩形范围内，被红雾遮盖的地区的数量。
输入输出格式
输入格式：
第一行三个整数n,m,q，表示幻想乡大小为n*m，有q个询问。
接下来q行，每行3个或5个整数,用空格隔开，含义见题目描述。
输出格式：
对于每一个操作2，输出一行一个整数，表示对应询问的答案。
输入输出样例
输入样例#1：
4 4 31 2 21 4 42 1 1 4 4
输出样例#1：
8
说明
样例解释:
用o表示没有红雾，x表示有红雾，两次释放红雾后幻想乡地图如下:
oxox
xoxo
oxox
xoxo
数据范围:
对于20%的数据，1<=n,m,q<=200
对于 40%的数据，1<=n,m,q<=1000
对于100%的数据，1<=n,m,q<=100000
1<=x1,x2,x<=n x1<=x2
1<=y1,y2,y<=m y1<=y2
by-orangebird
orangebird每次比赛都出线段树吗。 QAQ
加了小小容斥的线段树题
其实用树状数组更快吧
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 6 typedef long long ll; 7 8 inline int read(){ 9 char ch;10 int re=0;11 bool flag=0;12 while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘));13 ch==‘-‘?flag=1:re=ch-‘0‘;14 while((ch=getchar())>=‘0‘&&ch<=‘9‘) re=re*10+ch-‘0‘;15 return flag?-re:re;16 }17 18 struct segment{19 int l,r,num;20 };21 22 const int maxn=100001;23 24 segment tre[2][maxn<<2];25 int n,m,q;26 27 void push_up(int x,int c){28 tre[c][x].num=tre[c][x<<1].num+tre[c][x<<1|1].num;29 }30 31 void build(int x,int l,int r,int c){32 tre[c][x].l=l; tre[c][x].r=r;33 if(l==r) return;34 int mid=(l+r)>>1;35 build(x<<1,l,mid,c); build(x<<1|1,mid+1,r,c);36 }37 38 void update(int x,int pos,int c){39 if(tre[c][x].l==tre[c][x].r){40 tre[c][x].num^=1;41 return;42 }43 44 int mid=(tre[c][x].l+tre[c][x].r)>>1;45 if(mid>=pos) update(x<<1,pos,c);46 else update(x<<1|1,pos,c);47 push_up(x,c);48 }49 50 int query(int x,int L,int R,int c){51 if(L<=tre[c][x].l&&tre[c][x].r<=R) return tre[c][x].num;52 53 int mid=(tre[c][x].l+tre[c][x].r)>>1;54 if(R<=mid) return query(x<<1,L,R,c);55 if(L>mid) return query(x<<1|1,L,R,c);56 return query(x<<1,L,mid,c)+query(x<<1|1,mid+1,R,c);57 }58 59 int main(){60 //freopen("temp.in","r",stdin);61 n=read(); m=read(); q=read();62 build(1,1,n,1); build(1,1,m,0);63 int opt,x1,x2,y1,y2;64 ll ans1,ans2;65 for(int i=0;i<q;i++){66 opt=read();67 switch(opt){68 case 1:{69 x1=read(); y1=read();70 update(1,x1,1); update(1,y1,0);71 break;72 }73 case 2:{74 x1=read(); y1=read(); x2=read(); y2=read();75 ans1=query(1,x1,x2,1); ans2=query(1,y1,y2,0);76 printf("%lld\n",ans1*(ll)(y2-y1+1)+ans2*(ll)(x2-x1+1)-2LL*ans1*ans2);77 break;78 }79 }80 }81 }
我忘了置身濒绝孤岛
忘了眼泪不过是笑料
忘了百年无声口号
没能忘记你
[luogu P3801] 红色的幻想乡 [线段树][树状数组]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。