( ) 在手，谁敢卡我哈希？

#include <bits/stdc++.h>
#define ff fflush(stdout)
#define fop(i, l, r) for (int i = l; i <= r; ++i)
#define pof(i, r, l) for (int i = r; i >= l; --i)
#define edg(i, u) for (int i = head[u], v = to[i]; i; i = nxt[i], v = to[i])
typedef long long ll;
typedef unsigned long long ull;
#define int ll
const int inf = 0x3f3f3f3f3f3f3f3fll;
using namespace std;

int read() {
    int x = 0; bool f = 0; char c;
    while (!isdigit(c = getchar())) if (c == '-') f = 1;
    do x = (x << 1) + (x << 3) + (c ^ 48); while (isdigit(c = getchar()));
    return f ? -x : x;
}

const int maxn = 5e5 + 3;

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution<ull> rd(1, 1e7);
int rd_k = rd(rnd), rd_b = rd(rnd);

struct Hash {
	ull a, b, c, d;
	Hash() = default;
	void init() { a = b = c = d = 0; }
	Hash(ull x) {
		a = x * x * x - (x & 73) + (x ^ 19260817);
		b = (~x) * x + x * 19491001;
		c = rd_k * x + (rd_b ^ x);
		d = rd_k * rd_k * x + rd_b * x;
	}
	friend Hash operator +(const Hash &a, const Hash &b) {
		Hash c; return c.a = a.a + b.a, c.b = a.b + b.b, c.c = a.c + b.c, c.d = a.d + b.d, c;
	}
	void operator +=(const Hash &a) { *this = *this + a; }
	friend Hash operator -(const Hash &a, const Hash &b) {
		Hash c; return c.a = a.a - b.a, c.b = a.b - b.b, c.c = a.c - b.c, c.d = a.d - b.d, c;
	}
	void operator -=(const Hash &a) { *this = *this - a; }
	friend bool operator ==(const Hash &a, const Hash &b) {
		return a.a == b.a && a.b == b.b && a.c == b.c && a.d == b.d;
	}
} val[maxn], ori[maxn], sum[maxn], tot, res;

signed main() {
	int n = read(), m = read();
    fop(i, 1, n) val[i] = Hash(rd(rnd)), res += val[i];
    fop(i, 1, m) {
        int u = read(), v = read();
        sum[v] += val[u], ori[v] += val[u], tot += val[u];
    }
    int q = read();
    fop(i, 1, q) {
        int op = read(), u = read();
        if (op == 1) sum[read()] -= val[u], tot -= val[u];
        else if (op == 2) tot -= sum[u], sum[u].init();
        else if (op == 3) sum[read()] += val[u], tot += val[u];
        else tot += ori[u] - sum[u], sum[u] = ori[u];
        puts(tot == res ? "YES" : "NO");
    }
}

原文地址：http://www.cnblogs.com/eafoo/p/16878784.html