Submission #5073

#	Time	Username	Problem	Language	Result	Execution time	Memory
5073		cki86201	Collider (IZhO11_collider)	C++98	100 / 100	92 ms	19532 KiB

collider

#include<stdio.h>
#include<algorithm>
using namespace std;

const int N_ = 1e6 + 10;
const int inf = ~0u>>1;

//O(N + M lg N);
//이걸로 많이 우려먹는듯 ㅎㅎ

char inp[1000010];

class splaytree{
public:
	splaytree(int N){
		for(int i=0;i<N_;i++)ch[i][0] = ch[i][1] = down[i] = par[i] = 0;
		rev[0] = false, val[0] = 0;
		root = sz = 0;
		make_node(root, 0);
		make_node(ch[1][1], 0);
		par[ch[1][1]] = 1;
		down[1] = 2;
		build(1,N,ch[ch[root][1]][0],ch[root][1]);
		pushup(ch[root][1]), pushup(root);
	}
	int sz, root;
	int down[N_], ch[N_][2], par[N_];
	char val[N_];
	bool rev[N_];
	inline int dir(int x){return ch[par[x]][1] == x;}
	inline void make_node(int &p,char v){
		p = ++sz;
		ch[p][0] = ch[p][1] = rev[p] = 0;
		val[p] = v;
		down[p] = 1;
	}
	void build(int s,int d,int &p,int u){
		int m = (s+d)>>1;
		make_node(p, inp[m]);
		par[p] = u;
		if(s<m)build(s,m-1,ch[p][0],p);
		if(m<d)build(m+1,d,ch[p][1],p);
		pushup(p);
	}
	inline void pushup(int x){
		down[x] = down[ch[x][0]] + down[ch[x][1]] + 1;
	}
	inline void pushdown(int x){
		if(rev[x]){
			if(ch[x][0])rev[ch[x][0]]^=1;
			if(ch[x][1])rev[ch[x][1]]^=1;
			swap(ch[x][0],ch[x][1]);
			rev[x] = 0;
		}
	}
	inline void Rotate(int x){
		int y = par[x];
		pushdown(y), pushdown(x);
		int d = dir(x);
		ch[y][d] = ch[x][!d];
		par[ch[x][!d]] = y;
		ch[par[y]][dir(y)] = x;
		par[x] = par[y];
		par[y] = x, ch[x][!d] = y;
		pushup(y);
	}
	inline void splay(int x,int f){
		pushdown(x);
		while(par[x]!=f){
			if(par[par[x]] == f)Rotate(x);
			else if(dir(x) == dir(par[x]))Rotate(par[x]), Rotate(x);
			else Rotate(x), Rotate(x);
		}
		pushup(x);
		if(f == 0)root = x;
	}
	inline void kth_splay(int k,int f){
		int x = root;
		pushdown(x);
		while(down[ch[x][0]] != k){
			if(down[ch[x][0]] > k)x = ch[x][0];
			else k -= down[ch[x][0]]+1, x = ch[x][1];
			pushdown(x);
		}
		splay(x, f);
	}
	inline void Reverse(int x,int y){
		kth_splay(x-1,0);
		kth_splay(y+1,root);
		rev[ch[ch[root][1]][0]] ^= 1;
	}
	void quary(int x,int y){
		if(x<y){
			Reverse(x+1,y);
			Reverse(x,y);
		}
		else{
			Reverse(y,x-1);
			Reverse(y,x);
		}
	}
	char output(int x){
		kth_splay(x,0);
		return val[root];
	}
};

int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	scanf("%s",inp+1);
	splaytree st = splaytree(n);
	int i, x, y;
	char c[2];
	for(i=0;i<m;i++){
		scanf("%s",c);
		if(c[0] == 'a'){
			scanf("%d%d",&x,&y);
			st.quary(x,y);
		}
		else{
			scanf("%d",&x);
			printf("%c\n",st.output(x));
		}
	}
	return 0;
}

• Subtask 1: 100 / 100