注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4056][Ctsc2015]shallot  

2015-05-18 11:05:45|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4056: [Ctsc2015]shallot

Time Limit: 50 Sec  Memory Limit: 2560 MB
Submit: 7  Solved: 4
[Submit][Status][Discuss]

Description

小葱和小绪是一对好朋友,自从小葱11连出了1UR2SR之后,小绪就觉得小葱的人品特别好,于是小绪给小葱出了一道题来测试小葱的人品。 小绪首先在平面上画了N个点,分别是P1,P2,...,PN。
小绪把这N个点顺次相连,即连接(P1,P2),(P2,P3),...,(PN-1,PN),得到N-1条线段。 
之后小绪每次在平面上画出一条直线,然后问小葱这条直线与多少条线段相交。特别的,在线段端点处相交算作相交,直线完全覆盖线段时也算作相交。 这样的问题自然难不倒小葱,小葱只需要凭自己的人品用直觉就能给出正确的答案。 
小绪想测试小葱的人品究竟有多好,于是他加大了问题的难度: 除了每次询问以外,小绪会不时地讲一个新的点P插入到Pi和Pi+1之间,然后按照顺序对所有的点重新标记下标,即在Pi之后的点的下标会依次增加,而点P会变成新的点Pi+1。
特别的,点P也可以插入到第一个点之前或最后一个点之后。 
人品超级好的小葱依旧能够轻松的给出答案,于是小绪又进一步提高了难度: 
每次插入或提问之后,小绪都将操作后的所有线段记录了下来,称作一个历史版本。历史版本T表示在第T次操作后得到的历史版本。 
插入新点的操作改为了在某一个历史版本T的基础上,插入一个点P,并得到一个新的历史版本。 
小绪对小葱的提问改为了对于一个历史版本T,给出一条直线,询问这条直线会与多少条线段相交。 
小葱虽然人品很好,但面对这样的问题却也束手无策了,他只好找到来参加CTSC的你,请你来帮他解决这个问题。 

Input

第一行两个整数N,M,C『注:原文如此』,表示一开始的点数和总共的操作数,以及数据是否加密。
如果C=1,那么代表数据被加密过,每次询问操作中的X0,Y0,X,Y以及插入操作中的X,Y都是被加密过的数据,你需要将它们异或last_ans从而得到正确的数据,其中last_ans是上一次询问的答案,刚开始last_ans=0。 
接下来N行每行两个整数,其中第i行的两个整数表示Pi的横坐标和纵坐标。 
接下来M行,表示小绪的M次操作,其中第i行(从1开始标号)操作后得到的结果为历史版本i。 
对于每次操作,首先会有一个字母代表小绪的这次操作的操作类型。 
如果这个字母是'H',代表本次操作为一次询问操作。接下来会有五个整数T,X0,Y0,X,Y,代表在历史版本T的情况下,小绪给出一条经过(X0,Y0),方向为(X,Y)的直线,小葱要回答出它会和多少条直线相交。 
如果这个字母是'Z',代表本次操作为一次插入操作。接下来会有四个数T,i,X,Y,代表小绪在历史版本T的基础上,在Pi后面插入了一个坐标为(X,Y)的点。特别地,如果i=0,表示该点在P1之前。 

Output

要求对每一次询问操作,输出一行一个整数代表小葱应该回答的正确答案。 

Sample Input

2 3 0 0 0 1 1 H 0 1 0 -1 1 H 1 0 1 1 1 H 2 -1 -1 1 1

Sample Output

1 0 1

HINT

 样例解释: 

对于第三次询问,直线完全覆盖了线段,小绪会认为这也算相交。 
数据规模和约定: 
保证每次询问操作的T一定小于等于当前操作的数量,所有输入数据均为整数。
有以下4类特殊数据,它们两两没有交集: 
1.对于10%的数据,保证1<=N,M<=1000; 
2.对于15%的数据,保证对于第i次操作,T=i-1; 
3.对于15%的数据,保证C=0且不存在修改操作; 
4.对于15%的数据,对于询问操作,保证Y=0(加密过的数据指解密后的Y),即给出的直线平行于x轴。 
以上数据还保证1<=N,M<=5*104。 
对于100%的数据,保证1<=N,M<=105,所有的坐标范围在[-108,108]内,且每组数据中所有询问的答案总和不超过106,插入操作的次数不会超过5*104。注意这些线段可能会互相相交。

Solution

偶然机会有幸膜到了劼的代码,发现原来正解是可持久化平衡树套可持久化平衡树维护动态凸包,然后用矩形框来拟合凸包,这样做的话忽略掉了底层凸包的信息,但是代码非常可写,虽然一堆x=y的点就能卡。。。
于是这题就变成了可持久化Treap维护矩形信息

Code

/**************************************************************
    Problem: 4056
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:13380 ms
    Memory:143816 kb
****************************************************************/
 
#include<cstdio>
#include<cstdlib>
#define N 200010
typedef long long ll;
int n,m,type,i,aa,bb,x0,y0,x,y,rt[N],tot,cnt,ans,l,r,k;ll A,B,C;
char ch,buf[1<<15],*S=buf,*T=buf,op;
#define getc() (S==T&&(T=(S=buf)+fread(buf,1,1<<15,stdin),S==T)?0:*S++)
#define isd(c) (c>='0'&&c<='9')
int F(){
    while(ch=getc(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getc(),isd(ch))aa=aa*10+ch-'0';return bb?aa:-aa;
}
struct P{int x,y;}p[N];
struct T{int id,s[2],x[2],y[2],siz,l,r;}t[N*18];
#define ls t[o].s[0]
#define rs t[o].s[1]
#define cmax(a,b) (a<b?a=b:1)
#define cmin(a,b) (a>b?a=b:1)
void mt(int o){
    t[o].x[0]=t[o].x[1]=p[t[o].id].x;
    t[o].y[0]=t[o].y[1]=p[t[o].id].y;
    t[o].siz=t[ls].siz+t[rs].siz+1;
    t[o].l=t[o].r=t[o].id;
    if(ls){t[o].l=t[ls].l;
        cmin(t[o].x[0],t[ls].x[0]),cmax(t[o].x[1],t[ls].x[1]);
        cmin(t[o].y[0],t[ls].y[0]),cmax(t[o].y[1],t[ls].y[1]);
    }
    if(rs){t[o].r=t[rs].r;
        cmin(t[o].x[0],t[rs].x[0]),cmax(t[o].x[1],t[rs].x[1]);
        cmin(t[o].y[0],t[rs].y[0]),cmax(t[o].y[1],t[rs].y[1]);
    }
}
int merge(int x,int y){
    if(!x||!y)return x+y;int o=++tot;
    if(rand()%(t[x].siz+t[y].siz)<t[x].siz)t[o]=t[x],rs=merge(t[x].s[1],y);
    else t[o]=t[y],ls=merge(x,t[y].s[0]);
    return mt(o),o;
}
void split(int x,int k,int&l,int&r){
    if(!x){l=r=0;return;}
    int o=++tot;t[o]=t[x];
    if(t[ls].siz>=k)split(ls,k,l,r),ls=r,r=o;
    else split(rs,k-1-t[ls].siz,l,r),rs=l,l=o;
    mt(o);
}
#define calc(x,y) (A*x+B*y+C)
void check(int i,int j){
    if(!i||!j)return;
    ll d0=calc(p[i].x,p[i].y),d1=calc(p[j].x,p[j].y);
    if(d0>=0&&d1<=0||d0<=0&&d1>=0)ans++;
}
void query(int o){
    if(!o)return;
    check(t[o].id,t[ls].r),check(t[o].id,t[rs].l);
    ll d0=calc(t[o].x[0],t[o].y[0]),d1=calc(t[o].x[1],t[o].y[0]),
    d2=calc(t[o].x[1],t[o].y[1]),d3=calc(t[o].x[0],t[o].y[1]);