bzoj1062【Noi2008】糖果雨

首先给出的颜色没有用。

估计要用数据结构。而线段难以维护。

考虑把线段变成点

T是单增的。

所以询问的时候，存在的线段都可能贡献答案。

那些线段的位置如果可以统一一下就好了。

发现线段2*len一个循环

思路：把所有的线段移动到l=0

或者说，考虑l=0的时候，时间是多少

横坐标：x=(ti-d*l)%(2*len)（这个时间仅仅为了相对关系表示方便，实际上，这个线段可能根本不会在这个时间出现，不过没有关系）

纵坐标：y=r-l

这样的好处是，线段都是从l=0向右移动了

实际上坐标是多少，就意味着距离0还有多远

（看上面博客有图）

然后对于询问的t

分成一个图形，计算点的个数

转化为平行四边形

转化为矩形

二维树状数组维护

为了避免讨论

可以直接分成四块。不合法的直接面积返回0

注意时间轴的下标是从[0,2*len-1]的

所以树状数组还要集体平移1

细节较多。边界有些恶心

r==len的时候还要特别防止一个点统计两遍。

代码：

#include<bits/stdc++.h>

#define reg register int

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=+;

const int M=;

int n,len;

int mod;

struct node{

    int x,y1,y2;

}p[N];

int cnt;

int co[+];

struct at{

    int f[*M][*M];

    void add(int x,int y,int c){

        //swap(x,y);

        while(x<){

            int tmp=y;

            while(tmp<){

                f[x][tmp]+=c;

                tmp+=tmp&(-tmp);

            }

            x+=x&(-x);

        }

    }

    int query(int x,int y){

        //swap(x,y);

        if(x<||y<) return ;

        ++x,++y;

        if(x>=*len) x=*len;

        if(y>=*len) y=*len;

        int ret=;

    //    cout<<" x y "<<x<<" "<<y<<endl;

        while(x){

            int tmp=y;

            while(tmp){

                ret+=f[x][tmp];

                tmp-=tmp&(-tmp);

            }

            x-=x&(-x);

        }

        return ret;

    }

}t1,t2;

int get(int x1,int y1,int x2,int y2,int c){

//    cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<" "<<c-1<<endl;

    if(c==){

        int ret=t1.query(x2,y2)+t1.query(x1-,y1-)-t1.query(x1-,y2)-t1.query(x2,y1-);

    //    cout<<" ret "<<ret<<endl;

    return ret;

    }else{

        int ret=t2.query(x2,y2)+t2.query(x1-,y1-)-t2.query(x1-,y2)-t2.query(x2,y1-);

    //    cout<<" ret "<<ret<<endl;

    return ret;

    }

}

int sol(int t,int l,int r){

    int d=(r==len);

    return get(t,t+l,t+r,*len,)+get(,t+l-mod,t+r-mod-d,*len,)

        +get(t-r,l-t+mod,t-,*len,)+get(t-r+mod+d,l-t,mod-,*len,);

}

int main(){

    rd(n);rd(len);

    int op,t,c,l,r,d;

    mod=*len;

    while(n--){

        rd(op);

        if(op==){

            rd(t);rd(c);rd(l);rd(r);rd(d);

            ++cnt;

            p[cnt].x=(t-d*l+mod)%mod;

            p[cnt].y1=(r-l+p[cnt].x);

            p[cnt].y2=(r-l-p[cnt].x+mod);

        //    cout<<" point "<<p[cnt].x<<" "<<p[cnt].y1<<" || "<<p[cnt].y2<<endl;

            co[c]=cnt;

            t1.add(p[cnt].x+,p[cnt].y1+,);

            t2.add(p[cnt].x+,p[cnt].y2+,);

        }else if(op==){

            rd(t);rd(l);rd(r);

            t%=mod;

            printf("%d\n",sol(t,l,r));

        }else{

            rd(t);rd(c);

            t1.add(p[co[c]].x+,p[co[c]].y1+,-);

            t2.add(p[co[c]].x+,p[co[c]].y2+,-);

            co[c]=;

        }

    }

    return ;

}

}

signed main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2019/1/8 14:12:04

*/

转化还是鬼斧神工

方向就是抓住时间单增，统一出发位置考虑，mod意义下处理，线段变成点，方便维护。

不规则图形转化，坐标翻转。

同时避免讨论的小trick也不错。（这还是对水平要求比较高的）

巴特西

[NOI2008]糖果雨

bzoj1062【Noi2008】糖果雨

最新文章

热门文章