gym 101889 D
人生中的第一个分块题，竟然是训练赛的时候想不到其他该怎么做，又看到N很小，只有1e5，然后想了想好像平时说的是可行的复杂度，于是想了想分块的解法，然后比赛的时候WA在了第19组，是没有加假如这个块比查询区间大的时候，块把查询区间包含了，我们直接在该块内更新即可，还是太young。最后队友上直接1A了（比赛的时候我写没写出来，WA了3次，赛后才写出来呜呜呜）。
首先，其实我也没用过分块，在此之前，然后比赛的时候手推了个算法，好像优化到级别就可以做了，于是就往这方面想。
我们有长度为L的这么一串序列，0～L-1。然后我们有N次查询，每次将一个区间改变成为一种颜色，然后这个区间又是强制在线，这个是区间的两个端点，左取小、右取大。
然后我们可以分块考虑一下，如果包含了这整个块，我们可以直接对整个块添加lazy，否则就是在块内直接暴力，块内的复杂度也是，所以复杂度也是一定过的去的。现在，假如有这样的可能，就是我们包含了完整的一个块，但是块内的颜色五花八门了，我们该怎么搞呢？很多人会以为这样的复杂度是，其实不然，它仍然是的复杂度，因为如果有这样的区间，那么说明它之前一定是被作为某个不完全包含块来做修改的，这样的区间每次的操作最多两个，然后这样的区间的复杂度都是直接暴力即可的，所以又是。
所以最后的复杂度，就是，N次查询，每次改变的是的复杂度（上面的推理全都用了N，是为了方便写了QAQ）。
7 5 2 1 2 5 3 3 3 0 1 7 10 8 10 6 5 6 5 1 7 5 9 9 10 1 3 2 6 7 8 3 4 8 3 7 7 4 9 3 9 7 1 1 8 1000 2 3 5 2 3 719 4899 1 1 7143 7379 3 2 5611 5530 3 3 7944 5855 2 1 6962 5964 ans:1My Code：
#include <iostream> #include <cstdio> #include <cmath> #include <string> #include <cstring> #include <algorithm> #include <limits> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <unordered_map> #include <unordered_set> #define lowbit(x) ( x&(-x) ) #define pi 3.141592653589793 #define e 2.718281828459045 #define INF 0x3f3f3f3f #define eps 1e-6 #define HalF (l + r)>>1 #define lsn rt<<1 #define rsn rt<<1|1 #define Lson lsn, l, mid #define Rson rsn, mid+1, r #define QL Lson, ql, qr #define QR Rson, ql, qr #define myself rt, l, r using namespace std; typedef unsigned long long ull; typedef unsigned int uit; typedef long long ll; const int maxN = 1e5 + 7; int L, C, N, col[maxN] = {0}, len, s, its_col[maxN]; struct K { int l, r, lazy; inline int len() { return r - l + 1; } }t[maxN]; void update(int ql, int qr, int into_col) { int st = ql / len + 1, ed = qr / len + 1; int flag = into_col; if(st == ed) { if(t[st].lazy) { if(t[st].lazy == into_col) return; for(int i=t[st].l; i<=t[st].r; i++) { if(i >= ql && i <= qr) { col[t[st].lazy]--; col[into_col]++; its_col[i] = into_col; } else its_col[i] = t[st].lazy; if(flag && flag != its_col[i]) flag = 0; } } else { for(int i=t[st].l; i<=t[st].r; i++) { if(i >= ql && i <= qr) { col[its_col[i]]--; col[into_col]++; its_col[i] = into_col; } if(flag && flag != its_col[i]) flag = 0; } } t[st].lazy = flag; return; } flag = into_col; if(t[st].lazy) { for(int i=t[st].l; i<=t[st].r; i++) { if(i >= ql && i <= qr) { col[t[st].lazy]--; col[into_col]++; its_col[i] = into_col; } else its_col[i] = t[st].lazy; if(flag && flag != its_col[i]) flag = 0; } t[st].lazy = flag; } else { for(int i=t[st].l; i<=t[st].r; i++) { if(i >= ql && i <= qr) { col[its_col[i]]--; col[into_col]++; its_col[i] = into_col; } if(flag && flag != its_col[i]) flag = 0; } t[st].lazy = flag; } if(t[ed].lazy) { for(int i=t[ed].l; i<=t[ed].r; i++) { if(i >= ql && i <= qr) { col[t[ed].lazy]--; col[into_col]++; its_col[i] = into_col; } else its_col[i] = t[ed].lazy; if(flag && flag != its_col[i]) flag = 0; } t[ed].lazy = flag; } else { for(int i=t[ed].l; i<=t[ed].r; i++) { if(i >= ql && i <= qr) { col[its_col[i]]--; col[into_col]++; its_col[i] = into_col; } if(flag && flag != its_col[i]) flag = 0; } t[ed].lazy = flag; } for(int i = st + 1; i <= ed - 1; i++) { if(t[i].lazy) { col[t[i].lazy] -= t[i].len(); col[into_col] += t[i].len(); t[i].lazy = into_col; } else { flag = into_col; for(int j = t[i].l; j <= t[i].r; j++) { col[its_col[j]]--; col[into_col]++; its_col[j] = into_col; if(flag && flag != its_col[j]) flag = 0; } t[i].lazy = flag; } } } int main() { scanf("%d%d%d", &L, &C, &N); len = sqrt(L); for(int i=0; i<L; i++) its_col[i] = 1; s = L / len + (L % len == 0 ? 0 : 1); col[1] = L; for(int i=1; i<=s; i++) //左0，右L-1 { t[i].l = (i - 1) * len; t[i].r = i * len - 1; t[i].lazy = 1; } t[s].r = L - 1; int P, X; ll A, B, ans_L, ans_R, S; for(int i=1; i<=N; i++) { scanf("%d%d%lld%lld", &P, &X, &A, &B); S = col[P]; ans_L = (A + S * S % L) % L; ans_R = (A + (S + B) * (S + B) % L) % L; if(ans_L > ans_R) swap(ans_L, ans_R); update((int)ans_L, (int)ans_R, X); } int ans = 0; for(int i=1; i<=C; i++) ans = max(ans, col[i]); printf("%d\n", ans); return 0; }
