第一次居然hash被卡了。改了改rd()就A了。
题解：咱给每个人都随机一个数，几个人就是把他们的数异或起来，用set判重。再开一个set记录合法的房间。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 inline char nc() { 8 static char b[1<<16],*s=b,*t=b; 9 return s==t&&(t=(s=b)+fread(b,1,1<<16,stdin),s==t)?-1:*s++;10 }11 inline void read(int &x) {12 char b = nc(); x = 0;13 for (; !isdigit(b); b = nc());14 for (; isdigit(b); b = nc()) x = x * 10 + b - '0';15 }16 inline int op() {17 char b = nc(); for (; b != 'C' && b != 'W'; b = nc()); return b == 'C';18 }19 typedef unsigned long long ull;20 typedef ull bt;21 int n, m, q, p[100005], c[100005];22 const ull ULL_MAX = -1;23 bt a[100005], b[100005];24 inline ull rd() {25 return ull(rand()) * rand() * rand();26 }27 set < bt > h;28 set < int > s;29 int main() {30 read(n); read(m); read(q); srand(89513255); s.insert(1);31 for (int i = 1; i <= n; ++i) a[i] = rd(), p[i] = 1;32 for (int i = 1; i <= n; ++i) b[1] ^= a[i]; c[1] = n;33 for (int l, r, o, i = 0; i < q; ++i) {34 o = op(); read(l); read(r);35 if (o) {36 if (p[l] == r) continue;37 s.erase(p[l]); s.erase(r);38 b[p[l]] ^= a[l]; --c[p[l]];39 if (!h.count(b[p[l]])) s.insert(p[l]);40 b[r] ^= a[l]; ++c[r]; p[l] = r;41 if (!h.count(b[r])) s.insert(r);42 } else {43 int ans = 0; static set < int > :: iterator it; it = s.lower_bound(l);44 for (; it != s.end() && *it <= r; it = s.lower_bound(l)) {45 h.insert(b[*it]); ans += c[*it]; s.erase(it);46 } printf("%d\n", ans);47 }48 }49 return 0; 50 }