神题啊!干了一年才ac
首先由于各个操作的时间严格上升,因此在某此操作中,还没被删除的云朵是可以是为永久存在的;这样,又由于云的运动速度大小相同,即周期都为2len,将云的左端点一个周期的往返运动画在t(ime)-p(osition)图象上,类似下图中的蓝线;而红线即为云朵右端的图像。
(图片来源,侵删)
对于一个云朵ci=(t,colour,l,r,d),暴力模拟求出它的宽度、在0时刻(时间摸2len意义下)左端的位置及此时的运动方向,这样就能确定对应的左右折线,称他们为折线bi、ri。
对于询问qi=(t,l,r),可以看作求与线段(l,t)-(r,t)相交的不同云朵的折线数量。即sigma i [bi或ri与询问线段相交]的值,这可以更优美地表达为(sigma i [ri包含点(r,t)或者在点(r,t)左边])-(sigma i [bi在点(l,t)左边])。
所有时刻为正整数,涉及的所有点都为整点,可知式子的前后部分同质,即核心是求在包含某点或在某点左边的折线的数目。直接处理并不好做,可以考虑把坐标系旋转+平移,使得所有的折线段垂直或平行于坐标轴。例如
“在左边”变成了“在下边”,变得方便维护了,一个二维前缀和的形式。但我不清楚为什么有人单独维护r折线时,只用到了3*len的长宽,这应该是能被卡的。
#include <bits/stdc++.h> #define pt pair<int,int> #define mpt make_pair using namespace std; const int n=2e5+5; const int len=1e3+5; int n,len; int l[n],r[n],d[n]; int bit[2][4*len][4*len]; int sum(int cur,pt p,int w=0) { auto bit=::bit[cur]; for(int x=p.first; ; x-=x&-x) { for(int y=p.second; y>0; y-=y&-y) w+=bit[x][y]; w+=bit[x][0]; if(!x) break; } return w; } void add(int cur,pt p,int w) { auto bit=::bit[cur]; for(int x=p.first; x<=4*len; x+=x&-x) { for(int y=p.second; y<=4*len; y+=y&-y) { bit[x][y]+=w; if(!y) break; } if(!x) break; } } #define direct if(l==0) d=1; if(l==len) d=-1; pt rotate(int x,int y) {return mpt(x-y+2*len,x+y);} int main() { scanf("%d%d",&n,&len); for(int opt,t,c,l,r,d,s; n--; ) { scanf("%d%d",&opt,&t); t%=2*len; if(opt==1) { scanf("%d%d%d%d",&c,&l,&r,&d); r-=l; direct; for(; t; t%=2*len) { s=min(d>0?len-l:l,2*len-t); l+=d*s; t+=s; direct; } l[c]=l,r[c]=r,d[c]=d; for(s=0; t<2*len-1;) { l+=d*s; t+=s; direct; if(t==0&&d==1) { add(0,rotate(l,t),1); add(1,rotate(l+r,t),1); } else if(t==2*len-1&&((l<len&&d<0)||!l)) { add(0,rotate(l,t),1); add(1,rotate(l+r,t),1); } else if(0<t&&t<2*len-1) { add(0,rotate(l,t),d); add(1,rotate(l+r,t),d); } s=min(d>0?len-l:l,2*len-1-t); } } else if(opt==2) { scanf("%d%d",&l,&r); if(l==0) printf("%dn",sum(0,rotate(r,t))); else printf("%dn",sum(0,rotate(r,t))-sum(1,rotate(l-1,t))); } else if(opt==3) { scanf("%d",&c); l=l[c],r=r[c],d=d[c]; for(t=s=0; t<2*len-1;) { l+=d*s; t+=s; direct; if(t==0&&d==1) { add(0,rotate(l,t),-1); add(1,rotate(l+r,t),-1); } else if(t==2*len-1&&((l<len&&d<0)||!l)) { add(0,rotate(l,t),-1); add(1,rotate(l+r,t),-1); } else if(0<t&&t<2*len-1) { add(0,rotate(l,t),-d); add(1,rotate(l+r,t),-d); } s=min(d>0?len-l:l,2*len-1-t); } } } return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603248.html