Main » 2013 November 1 » 【CRAZY线段树】【NOIP2013模拟赛No.5】「永夜返 - 朝霭 -」
5:40 AM 【CRAZY线段树】【NOIP2013模拟赛No.5】「永夜返 - 朝霭 -」 |
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> #include<algorithm> #define lc(x) (x<<1) #define rc(x) ((x<<1)+1) #define PR pair<int,int> #define mp make_pair #define N 300010 #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) typedef long long LL; using namespace std; int S,Q; struct node { int l,r,lm,rm,col; int dis(){return r-l+1;} void calc() { if (col==1) lm=rm=dis(); if (col==0) lm=rm=0; } }; struct segtree { node tree[3*N]; void update(int x) { tree[x].lm=tree[lc(x)].lm; if (tree[lc(x)].lm==tree[lc(x)].dis()) tree[x].lm+=tree[rc(x)].lm; tree[x].rm=tree[rc(x)].rm; if (tree[rc(x)].rm==tree[rc(x)].dis()) tree[x].rm+=tree[lc(x)].rm; if (tree[lc(x)].col==1&&tree[rc(x)].col==1) tree[x].col=1; else if (tree[lc(x)].col==0&&tree[rc(x)].col==0) tree[x].col=0; else tree[x].col=-1; } void pushdown(int x) { if (tree[x].col==-1) return; if (tree[x].col==1) { tree[lc(x)].col=tree[rc(x)].col=1; tree[lc(x)].calc();tree[rc(x)].calc(); tree[x].col=-1; }else { tree[lc(x)].col=tree[rc(x)].col=0; tree[lc(x)].calc();tree[rc(x)].calc(); tree[x].col=-1; } } void build(int x,int L,int R) { tree[x].l=L;tree[x].r=R;int mid=(L+R)>>1; if (L==R){tree[x].col=1;tree[x].calc();return;} build(lc(x),L,mid);build(rc(x),mid+1,R); update(x); } void modify(int x,int L,int R,int D) { if (tree[x].l==L&&tree[x].r==R) { tree[x].col=D;tree[x].calc(); return; } pushdown(x); int mid=(tree[x].l+tree[x].r)>>1; if (R<=mid) modify(lc(x),L,R,D); else if (L>mid) modify(rc(x),L,R,D); else { modify(lc(x),L,mid,D); modify(rc(x),mid+1,R,D); } update(x); } int query_L(int x,int pos) { if (tree[x].l==tree[x].r) return tree[x].rm; int mid=(tree[x].l+tree[x].r)>>1; pushdown(x); if (pos<=mid) return query_L(lc(x),pos); if (pos>mid) { int t=query_L(rc(x),pos); if (t==pos-mid) { return t+tree[lc(x)].rm; }else return t; } } int query_R(int x,int pos) { if (tree[x].l==tree[x].r) return tree[x].lm; int mid=(tree[x].l+tree[x].r)>>1; pushdown(x); if (pos>mid) return query_R(rc(x),pos); if (pos<=mid) { int t=query_R(lc(x),pos); if (t==mid+1-pos) { return t+tree[rc(x)].lm; }else return t; } } }Tree; int main() { scanf("%d",&S); scanf("%d",&Q); Tree.build(1,1,S); int i; FOR(i,1,Q) { int op,L,R,p,res; scanf("%d",&op); if (op==1) { scanf("%d%d",&L,&R); Tree.modify(1,L,R,0); }else if (op==2) { scanf("%d%d",&L,&R); Tree.modify(1,L,R,1); }else { scanf("%d",&p); int le=Tree.query_L(1,p); int ri=Tree.query_R(1,p); if (le==0&&ri==0) res=0; else res=le+ri-1; if (p==le||S-p+1==ri) printf("INF\n"); else printf("%d\n",res); } } }
|
|
|
| Total comments: 0 | |