1 条题解

  • 0
    @ 2023-6-21 19:28:33

    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

    #503. 「邢台编程 β Round」ZQC 的课堂

    信息

    ID
    984
    时间
    4000ms
    内存
    512MiB
    难度
    10
    标签
    递交数
    2
    已通过
    2
    上传者