$rt$

拿到题目之后首先想到分块, 复杂度可以接受就写了

最后不论结果的话跑的也是挺快的

问题是自己写了对拍 小规模的数据完全拍不出来(大抵拍了12h) 至少要上万才会拍出来错误

蒟蒻危亡, 赖诸位神犇助力

代码贴上

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define re register

const int INF = 0x3f3f3f3f;
using namespace std;

struct book{
	int wk, wg;
};

book b[800050];
int n, m;
int k[500][500];
int l[500];
int sq = 495;
int tot, ftot = 166 * 500;

int main(){
	freopen("2596.in", "r", stdin);
	freopen("2596.out", "w", stdout); 
	cin >> n >> m;
	tot = n + ftot - 1;
	for (int i = n; i >= 1; i--){
		int a;
		cin >> a;
		k[(i + ftot - 1) / sq + 1][(i + ftot - 1) % sq] = a;
		b[a].wk = (i + ftot - 1) / sq + 1;
		b[a].wg = (i + ftot - 1) % sq;
		l[(i + ftot - 1) / sq + 1]++;  
	}
	while (m--){
		string opt;
		cin >> opt;
		if (opt == "Top"){
			int s, x, y;
			cin >> s;
			x = b[s].wk; y = b[s].wg; k[x][y] = 0; 
			l[x]--; tot++;
			x = tot / sq + 1; y = tot % sq;
			k[x][y] = s;
			b[s].wg = y; b[s].wk = x;
			l[x]++;
		}
		if (opt == "Bottom"){
			int s, x, y;
			cin >> s;
			x = b[s].wk; y = b[s].wg; k[x][y] = 0;
			l[x]--; ftot--;
			x = ftot / sq + 1; y = ftot % sq;
			k[x][y] = s;
			b[s].wg = y; b[s].wk = x;
			l[x]++;
		}
		if (opt == "Insert"){
			int s, t;
			cin >> s >> t;
			if (t == -1){
				int xs = b[s].wk, ys = b[s].wg;
				int flag = 0;
				for (re int i = ys + 1; i < sq; i++)
					if (k[xs][i] != 0){
						swap(b[s], b[k[xs][i]]);
						swap(k[xs][ys], k[xs][i]);
						flag = 1;
						break;
					}
				if (flag == 0)
					for (re int j = xs + 1; j <= sq; j++)
						if (l[j] != 0)
							for (re int i = 0; i < sq; i++)
								if (k[j][i] != 0){
									swap(b[s], b[k[j][i]]);
									swap(k[xs][ys], k[j][i]);
									break;
								}
			}
			if (t == 1){
				int xs = b[s].wk, ys = b[s].wg;
				int flag = 0;
				for (re int i = ys - 1; i >= 0; i--){
//					cout << k[xs][i] << " "; 
					if (k[xs][i] != 0){
						swap(b[s], b[k[xs][i]]);
						swap(k[xs][ys], k[xs][i]);
						flag = 1;
						break;
					}
				}
//				cout << endl;
				if (flag == 0)
					for (re int j = xs - 1; j >= 1; j--)
						if (l[j] != 0)
							for (re int i = sq - 1; i >= 0; i--)
								if (k[j][i] != 0){
									swap(b[s], b[k[j][i]]);
									swap(k[xs][ys], k[j][i]);
									break;
								}
			}
		}
		if (opt == "Ask"){
			int s, ans = 0;
			cin >> s;
			int xs = b[s].wk, ys = b[s].wg;
			for (re int i = ys + 1; i < sq; i++){
				if (k[xs][i] != 0)
					ans++;
			}
			for (re int i = xs + 1; i <= sq; i++)
				ans += l[i];
			cout << ans << endl;
		}
		if (opt == "Query"){
			int s, xs;
			cin >> s;
			for (re int i = sq; i > 0; i--){
				s -= l[i];
				if (s <= 0){
					s += l[i];
					xs = i;
					break;
				}
			}
			for (re int i = sq - 1; i >= 0; i--){
				if (k[xs][i] != 0) {
					s--;
					if (s == 0){
						cout << k[xs][i] << endl;
						break;
					}
				}
			}
		}
//		for (int i = 1; i <= sq; i++)
//			if (l[i] != 0)
//				for (int j = 0; j < sq; j++)
//					if (k[i][j] != 0) cout << k[i][j] << " ";
//		cout << endl;
	}	
	return 0;
}