提交记录

第一个点一直过不去，还有两个点RE

尝试卡常结果越卡越慢

1.06min —> 写了fread —> 1.07min —> 写了fwrite —> 1.08min —> 改了结构体的一些奇怪的东西，加了register —> 1.12min —> 1.13min。。。

我。。。

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize( \"inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falign-loops,-falign-labels,-fdevirtualize,-fcaller-saves,-fcrossjumping,-fthread-jumps,-funroll-loops,-freorder-blocks,-fschedule-insns,inline-functions,-ftree-tail-merge,-fschedule-insns2,-fstrict-aliasing,-fstrict-overflow,-falign-functions,-fcse-follow-jumps,-fsched-interblock,-fpartial-inlining,no-stack-protector,-freorder-functions,-findirect-inlining,-fhoist-adjacent-loads,-frerun-cse-after-loop,inline-small-functions,-finline-small-functions,-ftree-switch-conversion,-foptimize-sibling-calls,-fexpensive-optimizations,inline-functions-called-once,-fdelete-null-pointer-checks")
#include <bits/stdc++.h>

inline char getc() {
    static char buf[1<<21],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
}

inline int read() {
	register int j; char c;
	for (c = getc(); !isdigit(c); c = getc());
	for (j = 0; isdigit(c); j = (j << 1) + (j << 3) + (c ^ 48), c = getc());
	return j;
}

char buffer[1<<21];int p1=-1;const int p2 = (1<<21)-1;
inline void flush(){fwrite(buffer,1,p1+1,stdout),p1=-1;}
inline void putc(const char &x) {if(p1==p2)flush();buffer[++p1]=x;}

inline void write(int x) {
	static char c[20]; static int l = 0;
	do { c[++l] = x % 10 + 48; x /= 10; } while (x);
	for (; l; --l) { putc(c[l]); }
}

inline int max(int x, int y) { return x > y ? x : y; }
inline int min(int x, int y) { return x < y ? x : y; }

const int N = 1e6 + 10;
const int M = 5e5 + 10;
const int block = 1e3;

struct Node {
	int opt, l, r, x;
} q[M];

int n, m, cnt, tag, maxn, L, R, X, ql, qr;
int a[N], l[block + 5], r[block + 5], f[N], v[N], g[N], tot[N], ans[M];

inline int find(int x) {
	while (x != f[x]) {
		f[x] = f[f[x]]; x = f[x];
	} return x;
}

inline void Marry(int x, int y) {
	if (v[y]) { f[v[x]] = v[y]; }
	else { v[y] = v[x]; g[v[y]] = y; }
	tot[y] += tot[x];
	tot[x] = v[x] = 0;
}

inline void Build(int x) {
	maxn = tag = 0;
	memset(v, 0, sizeof v);
	memset(tot, 0, sizeof tot);
	for (register int i = ql; i <= qr; i++) {
		maxn = max(maxn, a[i]);
		if (v[a[i]]) { f[i] = v[a[i]]; }
		else {
			f[i] = v[a[i]] = i;
			g[i] = a[i];
		}
		tot[a[i]]++;
	}
}

inline void Modify() {
	if (maxn - tag >= (X << 1)) {
		for (register int i = tag + 1; i <= tag + X; i++) {
			if (v[i]) { Marry(i, i + X); }
		}
		tag += X;
	} else {
		for (register int i = X + tag + 1; i <= maxn; i++) {
			if (v[i]) { Marry(i, i - X); }
		}
		maxn = tag + X;
	}
}

inline void ReBuild(int x) {
	for (register int i = ql; i <= qr; i++) {
		a[i] = g[find(i)];
		tot[a[i]] = v[a[i]] = 0;
		a[i] -= tag;
	}
	for (register int i = ql; i <= qr; i++) { g[i] = 0; }
	int q = min(qr, R);
	for (register int i = max(ql, L); i <= q; i++) {
		if (a[i] > X) { a[i] -= X; }
	}
	maxn = tag = 0;
	for (register int i = ql; i <= qr; i++) {
		maxn = max(maxn, a[i]);
		if (v[a[i]]) { f[i] = v[a[i]]; }
		else {
			f[i] = v[a[i]] = i;
			g[i] = a[i];
		}
		tot[a[i]]++;
	}
}

inline void query(int x, int j) {
	if (X + tag > 1e5 + 1) { return ; }
	if (ql >= L && qr <= R) { ans[j] += tot[X + tag]; return ; }
	int q = min(qr, R);
	for (register int i = max(ql, L); i <= q; i++) {
		if (g[find(i)] == X + tag) { ans[j]++; }
	}
}

signed main() {
	n = read(); m = read();
	cnt = n / block + (n % block != 0); 
	for (register int i = 1; i <= n; i++) { a[i] = read(); }
	for (register int i = 1; i <= cnt; i++) {
		l[i] = r[i - 1] + 1;
		r[i] = l[i] + block - 1;
	} r[cnt] = n;
	for (register int i = 1; i <= m; i++) {
		q[i].opt = read();
		q[i].l = read(); q[i].r = read();
		q[i].x = read();
	}
	for (register int i = 1; i <= cnt; i++) {
		ql = l[i]; qr = r[i]; Build(i);
		for (register int j = 1; j <= m; j++) {
			L = q[j].l; R = q[j].r; X = q[j].x;
			if (R < ql || L > qr) { continue; }
			if (q[j].opt == 1) {
				if (ql >= L && qr <= R) { Modify(); }
				else { ReBuild(i); }
			} else { query(i, j); }
		}
	}
	for (register int i = 1; i <= m; i++) {
		if (q[i].opt == 2) { write(ans[i]); putc('\n'); }
	}
	flush();
	return 0;
}