C++14(g++5.4) 解法, 执行用时: 337ms, 内存消耗: 4332K, 提交时间: 2020-03-22 19:15:26

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn=5e6+10;
int n,m,num,l,r,cnt,id,top;
char s[maxn],sta[maxn],q[maxn],ans[maxn];
int main()
{
	scanf("%d%d%d%s",&n,&m,&num,s+1); l=2e6; r=2e6-1; id=1;
	for (int i=1;i<=m;i++) q[++r]=s[i];
	while (num--)
	{
		int op,lc; scanf("%d%d",&op,&lc);
		if (op==2)
		{
			if (lc<=top) ans[++cnt]=sta[lc];
			else if (lc<=top+m)
			{
				lc-=top;
				if (l>r) ans[++cnt]=q[l-lc+1];else ans[++cnt]=q[l+lc-1];
			}
			else ans[++cnt]=s[lc];
		}
		else
		{
			while (id<lc)
			{
				id++;
				if (l<=r) sta[++top]=q[l++],q[++r]=s[id+m-1];else sta[++top]=q[l--],q[--r]=s[id+m-1];
			}
			swap(l,r);
		}
	}
	for (int i=1;i<=cnt;i++) printf("%c",ans[i]);
return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 235ms, 内存消耗: 3684K, 提交时间: 2020-03-21 08:29:55

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+50;
int n,m,q,p;char s[N],ans[N];bool re;
struct Que{
	int l,r;char a[N];
	void pub(int x){a[++r]=x;}
	void puf(int x){a[--l]=x;}
	void pob(){r--;}
	void pof(){l++;}
	int b(){return a[r];}
	int f(){return a[l];}
}qq;
int main(){
	scanf("%d%d%d%s",&n,&m,&q,s+1);qq.l=1e6+10;qq.r=qq.l-1;
	for(int i=1;i<=m;i++)qq.pub(s[i]);
	for(int i=1,op,x,j=1;i<=q;i++){
		scanf("%d%d",&op,&x);
		if(op==1){
			while(j<x)
				if(re) s[j++]=qq.b(),qq.pob(),qq.puf(s[j+m-1]);
				else s[j++]=qq.f(),qq.pof(),qq.pub(s[j+m-1]);
			re^=1;
		}
		else ans[++p]=x<j||x>=j+m?s[x]:re?qq.a[qq.l+j+m-x-1]:qq.a[qq.l+x-j];
	}
	printf("%s",ans+1);
	return 0;
}