1 条题解
-
0
C++ :
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int SIZEN = 100010; struct Vector{int x,y;}v[SIZEN]; struct Ask{char opt[5];int x,y;}q[SIZEN*3]; int N,Q,it=1; int seq[SIZEN]={0},delta = 0; int mi[SIZEN]={0},mx[SIZEN]={0}; int ans[SIZEN*3]={0},sum1,sum2; //sum1 : max less zero, sum2 : min greater zero #define SIZE(x) (x?x->size:0) struct Treap{ struct Node{ Node *ch[2]; int size,pre,val; void Maintain(){size = SIZE(ch[0])+SIZE(ch[1])+1;} }mem[SIZEN*2],*p,*del[SIZEN*2],*root; int top; Treap(){p = mem;root = NULL;top=0;} Node *newnode(int x){ Node *rt = top?del[top--]:p++; rt->ch[0] = rt->ch[1] = NULL; rt->size = 1; rt->pre = rand();rt->val = x; return rt; } void Rotate(Node *&rt,int k){ Node *y = rt->ch[k^1]; rt->ch[k^1] = y->ch[k]; y->ch[k] = rt; rt->Maintain(); y->Maintain(); rt = y; } void insert(int x){insert(x,root);} void insert(int x,Node *&rt){ if(!rt){rt = newnode(x);return;} int k = x >= rt->val; insert(x,rt->ch[k]);rt->Maintain(); if(rt->ch[k]->pre > rt->pre)Rotate(rt,k^1); } void erase(int x){erase(x,root);} void erase(int x,Node *&rt){ if(rt->val == x){ if(rt->ch[0] && rt->ch[1]){ int k = rt->ch[0]->pre > rt->ch[1]->pre; Rotate(rt,k);erase(x,rt->ch[k]); } else { Node *y = NULL; y = rt->ch[0]?rt->ch[0]:rt->ch[1]; del[++top] = rt;rt = y; } } else erase(x,rt->ch[x>=rt->val]); if(rt)rt->Maintain(); } int rank(int x){ Node *rt = root; int ret = 0; while(rt){ if(rt->val <= x)ret += SIZE(rt->ch[0])+1,rt=rt->ch[1]; else rt = rt->ch[0]; } return ret; } }tmin,tmax; void back(int x){ mx[x] = max(seq[x],seq[x-1]); mi[x] = min(seq[x],seq[x-1]); if(mx[x] < 0)sum1--;if(mi[x] > 0)sum2--; mx[x] -= delta;mi[x] -= delta; tmin.insert(mi[x]);tmax.insert(mx[x]); } void front(int x){ tmin.erase(mi[x]);tmax.erase(mx[x]); if(mx[x]+delta<0)sum1++;if(mi[x]+delta>0)sum2++; if(mx[x]+delta == seq[x-1])seq[x] = mi[x]+delta; if(mi[x]+delta == seq[x-1])seq[x] = mx[x]+delta; } void change(int x){ front(it++); delta += x-(seq[it-1]-seq[it-2]); if(max(seq[it-1],seq[it-2]) < 0)sum1--; if(min(seq[it-1],seq[it-2]) > 0)sum2--; seq[it-1] = seq[it-2]+x; if(max(seq[it-1],seq[it-2]) < 0)sum1++; if(min(seq[it-1],seq[it-2]) > 0)sum2++; back(--it); } void query(int i){ int k = (N-it+1)-tmin.rank(-delta); k += tmax.rank(-delta); k += sum1+sum2; ans[i] -= k; } inline void read(int &x){ x=0;static char ch;static bool flag;flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x; } void read(){ read(N); for(register int i = 1;i <= N;i++)read(v[i].x),read(v[i].y); read(Q); for(register int i = 1;i <= Q;i++){ scanf("%s",q[i].opt); if(q[i].opt[0] == 'C')read(q[i].x),read(q[i].y); } seq[0] = 1;it = N+1; for(register int i = 1;i <= Q;i++)ans[i] = N+N; } void work(){ while(it <= N)front(it++); it = 1;delta = 0;sum1=0;sum2=0; for(register int i = 1;i <= N;i++){ seq[i] += seq[i-1]; mi[i] = min(seq[i],seq[i-1]); mx[i] = max(seq[i],seq[i-1]); tmin.insert(mi[i]);tmax.insert(mx[i]); } for(register int i = 1;i <= Q;i++){ switch(q[i].opt[0]){ case 'B':if(it!=1)back(--it);break; case 'F':if(it!=N)front(it++);break; case 'C':change(q[i].x);break; case 'Q':query(i);break;} } } int main(){ read(); for(register int i = 1;i <= N;i++)seq[i] = v[i].x; for(register int i = 1;i <= Q;i++)q[i].x = q[i].x; work(); for(register int i = 1;i <= N;i++)seq[i] = v[i].y; for(register int i = 1;i <= Q;i++)q[i].x = q[i].y; work(); for(register int i = 1;i <= Q;i++)if(q[i].opt[0] == 'Q')printf("%d\n",ans[i]); return 0; }
- 1
信息
- ID
- 984
- 时间
- 4000ms
- 内存
- 512MiB
- 难度
- 10
- 标签
- 递交数
- 2
- 已通过
- 2
- 上传者