C++11(clang++ 3.9) 解法, 执行用时: 670ms, 内存消耗: 416480K, 提交时间: 2018-11-16 18:05:38

#include<bits/stdc++.h>
using namespace std;

int rand_int()
{
	return RAND_MAX<=32768?rand()*32768+rand():rand();
}
const int N=1e5+5;
struct Node
{
	Node *cl,*cr;
	bool exist,val,rev;
	int sz,cnt1;
	void push_up()
	{
		sz=exist;cnt1=val;
		if(cl){sz+=cl->sz;cnt1+=cl->cnt1;}
		if(cr){sz+=cr->sz;cnt1+=cr->cnt1;}
	}
};
Node *rt,q[N*200],*tail=q;
Node *newNode(bool v)
{
	++tail;
	tail->exist=1;
	tail->cnt1=tail->val=v;
	tail->sz=1;
	return tail;
}
Node *copy(Node *x)
{
	*++tail=*x;
	return tail;
}
Node *failNode(Node *l,Node *r)
{
	++tail;
	tail->cl=l;tail->cr=r;
	tail->push_up();
	return tail;
}
void push_down(Node *x)
{
	if(x->rev)
	{
		x->rev=0;
		swap(x->cl,x->cr);
		if(x->cl)(x->cl=copy(x->cl))->rev^=1;
		if(x->cr)(x->cr=copy(x->cr))->rev^=1;
	}
}
Node *merge(Node *a,Node *b)
{
	if(!a)return b;
	if(!b)return a;
	if(rand_int()%(a->sz+b->sz)<a->sz)
	{
		push_down(a);
		a=copy(a);
		a->cr=merge(a->cr,b);
		a->push_up();
		return a;
	}
	else
	{
		push_down(b);
		b=copy(b);
		b->cl=merge(a,b->cl);
		b->push_up(); 
		return b;
	}
}
void split(Node *a,int k,Node *&l,Node *&r)
{
	if(!k){l=0;r=a;return ;}
	push_down(a);
	a=copy(a);
	int l_sz=a->cl?a->cl->sz:0;
	if(k<=l_sz)
	{
		split(a->cl,k,l,r);
		a->cl=r;
		r=a;
	}
	else
	{
		split(a->cr,k-(l_sz+a->exist),l,r);
		a->cr=l;
		l=a;
	}
	a->push_up();
}
char s[N];
Node *build(int l,int r)
{
	if(l>r)return 0;
	int mid=(l+r)/2;
	Node *x=newNode(s[mid]=='1');
	x->cl=build(l,mid-1);
	x->cr=build(mid+1,r);
	x->push_up();
	return x;
}
int query(int k)
{
	if(k>rt->cnt1)return -1;
	int ans=0;
	Node *x=rt;
	while(1)
	{
		push_down(x);
		int l_cnt1=x->cl?x->cl->cnt1:0;
		if(k<=l_cnt1)x=x->cl; else
		{
			ans+=(x->cl?x->cl->sz:0)+x->exist;
			k-=l_cnt1+x->val;
			if(!k)break;
			x=x->cr;
		}
	}
	return ans;
}

int main()
{
#ifdef kcz
	freopen("1.in","r",stdin);freopen("1.out","w",stdout);
#endif
	int n;
	cin>>n;
	scanf("%s",s+1);
	rt=build(1,n);
	int m;
	cin>>m;
	while(m--)
	{
		int op;
		scanf("%d",&op);
		if(op==4)
		{
			int k;
			scanf("%d",&k);
			printf("%d\n",query(k));
			continue;
		}
		int l,r;
		scanf("%d%d",&l,&r);
		Node *a0,*a1;
		split(rt,l-1,a0,a1);
		Node *p,*a2;
		split(a1,r-l+1,p,a2);
		if(op==3)
		{
			rt=merge(a0,a2);
			continue;
		}
		int k;
		scanf("%d",&k);
		Node *np=copy(p);
		if(op==2)np->rev^=1;
		int i=1;
		for(;i<k;i*=2)
		{
			Node *p1=failNode(p,np),*np1=failNode(np,p);
			p=p1;np=np1;
			p->push_up();
			np->push_up();
		}
		Node *pl,*pr;
		split(p,k*(r-l+1),pl,pr);
		rt=merge(a0,merge(pl,a2));
	}
}