当前位置： 移动技术网 > IT编程>开发语言>C/C++ > [NOI2008] 糖果雨

[NOI2008] 糖果雨

2019年05月28日  | 移动技术网IT编程  | 我要评论

天桥区民政局,武松卡盟官网,战歌dj

神题啊！干了一年才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("%d\n",sum(0,rotate(r,t)));
            else printf("%d\n",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;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网