提交记录 3539


用户 题目 状态 得分 用时 内存 语言 代码长度
Cydiater noi17b. 【NOI2017】蚯蚓排队 Accepted 100 886.924 ms 109568 KB C++ 2.84 KB
提交时间 评测时间
2018-07-16 14:22:59 2020-07-31 21:19:08
#include <bits/stdc++.h>

using namespace std;

#define ll 			long long
#define db			double
#define ull			unsigned long long
#define up(i,j,n)		for (int i = j; i <= n; i++)
#define down(i,j,n)	for (int i = j; i >= n; i--)
#define cadd(a,b)		a = add (a, b)
#define cpop(a,b)		a = pop (a, b)
#define cmul(a,b)		a = mul (a, b)
#define pr			pair<int, int>
#define fi			first
#define se			second
#define SZ(x)		(int)x.size()
#define Auto(i,node)	for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}

const int mod = 998244353;
const int MOD = 10002333;

const ull step = 17171717;

const int MAXN = 2e5 + 5;
const int MAXM = 1e7 + 5;

inline int add(int a, int b){a += b; return a >= mod ? a - mod : a;}
inline int pop(int a, int b){a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b){return 1LL * a * b % mod;}

struct H {
	struct edge {
		int next, v;
		ull q;
	}e[MOD + MOD];
	int LINK[MOD], len;
	inline void ins(int p, ull q, int v){
		e[++len].next = LINK[p]; LINK[p] = len;
		e[len].q = q; e[len].v = v;
	}
	int get(ull x){
		int p = x % MOD;
		Auto (i, p) if (e[i].q == x) return e[i].v;
		return 0;
	}
	void cg(ull x, int v){
		int p = x % MOD;
		Auto (i, p) if (e[i].q == x) return (void) (e[i].v += v);
		ins(p, x, v);
	}
}S;

ull bin[MAXN];

int N, Q;

struct LK {
	int pre, nxt, v;
}a[MAXN];

int pre[MAXN], suf[MAXN];

char s[MAXM];

int main(){
	scanf("%d%d", &N, &Q);
	up (i, 1, N) {
		scanf("%d", &a[i].v);
		S.cg(a[i].v, 1);
	}
	bin[0] = 1;
	up (i, 1, N) bin[i] = bin[i - 1] * step;
	while (Q--) {
		int o, x, y;
		scanf("%d", &o);
		if (o == 1) {
			scanf("%d%d", &x, &y);
			int p = 0, q = 0;
			a[x].nxt = y; a[y].pre = x;
			for (int i = x; i && p < 50; i = a[i].pre) pre[++p] = a[i].v;
			for (int i = y; i && q < 50; i = a[i].nxt) suf[++q] = a[i].v;
			up (i, 1, p) {
				int n = min(q, 50 - i);
				ull cur = 0;
				down (j, i, 1) cur = cur * step + pre[j];
				up (j, 1, n) {
					cur = cur * step + suf[j];
					S.cg(cur, 1);
				}
			}
		} 
		if (o == 2) {
			scanf("%d", &x); y = a[x].nxt;
			int p = 0, q = 0;
			for (int i = x; i && p < 50; i = a[i].pre) pre[++p] = a[i].v;
			for (int i = y; i && q < 50; i = a[i].nxt) suf[++q] = a[i].v;
			up (i, 1, p) {
				int n = min(q, 50 - i);
				ull cur = 0;
				down (j, i, 1) cur = cur * step + pre[j];
				up (j, 1, n) {
					cur = cur * step + suf[j];
					S.cg(cur, -1);
				}
			}
			a[x].nxt = 0; a[y].pre = 0;
		}
		if (o == 3) {
			scanf("%s%d", s + 1, &x); int len = strlen(s + 1);
			ull cur = 0;
			up (i, 1, x - 1) cur = cur * step + (s[i] - '0');
			int ans = 1;
			up (i, x, len) {
				cur = cur * step + (s[i] - '0');
				if (i > x) cur -= bin[x] * (s[i - x] - '0');
				cmul(ans, S.get(cur));
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1367.72 us56 KBAcceptedScore: 4

Testcase #289.63 us336 KBAcceptedScore: 4

Testcase #37.894 ms5 MB + 528 KBAcceptedScore: 4

Testcase #41.404 ms10 MB + 816 KBAcceptedScore: 4

Testcase #57.035 ms14 MB + 496 KBAcceptedScore: 4

Testcase #6126.796 ms57 MB + 932 KBAcceptedScore: 4

Testcase #718.292 ms1 MB + 208 KBAcceptedScore: 4

Testcase #875.318 ms54 MB + 944 KBAcceptedScore: 4

Testcase #9131.486 ms58 MB + 820 KBAcceptedScore: 4

Testcase #10139.445 ms55 MB + 1008 KBAcceptedScore: 4

Testcase #11261.503 ms63 MB + 712 KBAcceptedScore: 4

Testcase #12139.234 ms61 MB + 264 KBAcceptedScore: 4

Testcase #1337.204 ms2 MB + 168 KBAcceptedScore: 4

Testcase #14165.791 ms69 MB + 112 KBAcceptedScore: 4

Testcase #15212.894 ms71 MB + 608 KBAcceptedScore: 4

Testcase #16311.252 ms71 MB + 584 KBAcceptedScore: 4

Testcase #17459.897 ms78 MB + 512 KBAcceptedScore: 4

Testcase #18594.274 ms100 MB + 960 KBAcceptedScore: 4

Testcase #19688.128 ms107 MBAcceptedScore: 4

Testcase #20134.242 ms56 MB + 312 KBAcceptedScore: 4

Testcase #2176.957 ms4 MB + 72 KBAcceptedScore: 4

Testcase #22388.854 ms95 MB + 344 KBAcceptedScore: 4

Testcase #23427.019 ms96 MB + 428 KBAcceptedScore: 4

Testcase #24715.073 ms100 MB + 164 KBAcceptedScore: 4

Testcase #25886.924 ms106 MB + 700 KBAcceptedScore: 4


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 08:12:05 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用