c/c++语言开发共享[NOI2008] 糖果雨

神题啊！干了一年才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; }