http://www.lydsy.com/JudgeOnline/problem.php?id=1062
思路:找到平行四边形以后,变换坐标:y->y-kx,k为斜率,这样变成了矩形,然后只要二维树状数组就行了、
注意可能因为取余的原因,把一个平行四边形拆成两半
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
int len2,len,len4,n;
int tr[][][];
int x[],y[];
int lowbit(int X){
return (X)&(-X);
}
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void add(int k,int x,int y,int c){
x++;y++;
for (int i=x;i<=len2;i+=lowbit(i))
for (int j=y;j<=len4;j+=lowbit(j))
tr[k][i][j]+=c;
}
int sum(int k,int x,int y){
if (x<||y<) return ;
x++;y++;
int ans=;
if (x>len2) x=len2+;
if (y>len4) y=len4+;
for (int i=x;i;i-=lowbit(i))
for (int j=y;j;j-=lowbit(j))
ans+=tr[k][i][j];
return ans;
}
int sum(int k,int x1,int y1,int x2,int y2){
return sum(k,x2,y2)+sum(k,x1-,y1-)-sum(k,x2,y1-)-sum(k,x1-,y2);
}
int main(){
n=read();len=read();len2=len<<;len4=len2<<;
while (n--){
int opt=read();
if (opt==){
int t=read(),c=read(),l=read(),r=read(),d=read();
x[c]=(t-d*l+len2)%len2;
y[c]=r-l;
add(,x[c],y[c]+x[c],);
add(,x[c],y[c]-x[c]+len2,);
}else
if (opt==)
{
int t=read(),l=read(),r=read();
t%=len2;
int k=(r==len);
int ans=sum(,t,l+t,r+t,len4)+sum(,,l+t-len2,r+t-len2-k,len4)
+sum(,t-r+len2+k,l-t,len2,len4)+sum(,t-r,l-t+len2,t-,len4);
printf("%d\n",ans);
}else{
int t=read(),c=read();
add(,x[c],y[c]+x[c],-);
add(,x[c],y[c]-x[c]+len2,-);
}
} }