题意：每次操作将区间颜色置为x，要求可以查询某个颜色出现次数，强制在线，求最后出现次数最多的颜色的次数。
分析：考虑分块做法。
对于每个块记录一个laz，laz为0表示这个块中的颜色不唯一，否则表示该颜色。
更新时两端暴力更新，若整块的laz不为0，直接O(1)得到，否则暴力更新。
分析一下复杂度，两端暴力更新O(n^1/2)，laz不为0的块O(1)，laz为0的块O(n^1/2)。
同时每次更新仅仅会产生2个laz为0的块，当laz为0的块经过一次暴力更新后，laz必然不为0，所以总共暴力更新整块的次数不会超过2n次。所以复杂度O(n*sqrt(n))。
#include <bits/stdc++.h> using namespace std; const int mod = 1e9 + 7; int mat, num; int a[100004]; int L[350], R[350]; int col[100004]; int laz[350]; void upd(int l, int r, int x) { int st = l / mat + 1; int ed = r / mat + 1; if(st == ed){ if(laz[st]) for (int i = L[st]; i <= R[st]; ++i) { a[i] = laz[st]; } laz[st]=0; for (int i = l; i <= r; ++i) { col[a[i]]--; col[x]++; a[i]=x; } return; } st ++; ed --; for (int i = st; i <= ed; ++i) { if (laz[i]) { col[laz[i]] -= R[i] - L[i] + 1; col[x] += R[i] - L[i] + 1; laz[i] = x; } else { for (int j = L[i]; j <= R[i]; ++j) { col[a[j]]--; col[x]++; a[j] = x; } laz[i] = x; } } if (laz[st - 1]) for (int i = L[st - 1]; i <= R[st - 1]; ++i) { a[i] = laz[st - 1]; } laz[st - 1] = 0; if (laz[ed + 1]) for (int i = L[ed + 1]; i <= R[ed + 1]; ++i) { a[i] = laz[ed + 1]; } laz[ed + 1] = 0; for (int i = l; i < L[st]; ++i) { col[a[i]]--; col[x]++; a[i] = x; } for (int i = R[ed]+1; i <= r; ++i) { col[a[i]]--; col[x]++; a[i] = x; } } int main() { int l, c, n; memset(col, 0, sizeof(col)); scanf("%d%d%d", &l, &c, &n); mat = sqrt(l); num = (l + mat - 1) / mat; for (int i = 1; i <= num; ++i) { laz[i] = 1; L[i] = (i - 1) * mat; R[i] = i * mat - 1; } for (int i = 0; i < l; ++i) { a[i] = 1; } R[num] = l - 1; col[1] = l; for (int i = 0; i < n; ++i) { long long p, x, a, b; scanf("%lld%lld%lld%lld", &p, &x, &a, &b); long long s = col[p]; long long m1 = (a + s * s % l) % l; long long m2 = (a + (s + b) * (s + b) % l) % l; if (m1 > m2)swap(m1, m2); upd(m1, m2, x); } int ans = 0; for (int i = 1; i <= c; ++i) { ans = max(ans,col[i]); } cout<<ans<<endl; }
