Solution
非常巧妙的建立DP方程。
据dalao们说题目明显暗示根号复杂度？？（反正我是没看出来
因为每次分的块大小一定不超过$\sqrt n$，要不然直接每个位置开一个块答案都才为$n$。
于是大佬们想到用一个非常巧妙的数组$pos[j]$，表示顺推到当前位置$i$时，以$i$作为右端点，区间出现了$j$个颜色的左端点的位置。
于是每次转移就变成了$dp[i]=min(dp[pos[j]-1]+j*j)$，而不需要把之前全部枚举。$j$的范围就是$<=\sqrt n$的。
所以每次新到一个位置，就对于每个$j$看是否有新的贡献，记录$cnt[j]$表示$pos[j]$到$i$当前实际有多少个颜色。
如果$cnt[j]>j$表示当前$pos[j]$需要往后移动更新，那么每次往后一位一位暴力移动查询当前位置是否可以作为$pos[j]$，就是判断这个位置之后，$i$之前是否还出现了这个位置的颜色，如果出现了那么这个位置就不能作为$pos[j]$，因为它后面还有贡献。（据说均摊复杂度O(n)？？）
细节通过双向链表处理。
Code
#include<bits/stdc++.h>
#define LL long long
#define RG register
using namespace std; LL dp[];
int nxt[], a[], pre[], las[], pos[], cnt[];
int n, m; int main() {
freopen("cleanup.in", "r", stdin);
freopen("cleanup.out", "w", stdout);
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i ++) {
scanf("%d", &a[i]);
pre[i] = las[a[i]];
nxt[las[a[i]]] = i;
las[a[i]] = i;
nxt[i] = n + ;
}
memset(dp, 0x3f3f3f3f, sizeof(dp)); dp[] = ;
int siz = sqrt(n); for(int i = ; i <= siz; i ++) pos[i] = ;
for(RG int i = ; i <= n; i ++) {
for(RG int j = ; j <= siz; j ++) {
if(pre[i] < pos[j]) cnt[j] ++;
if(cnt[j] > j) {
cnt[j] --;
while(nxt[pos[j]] < i) pos[j] ++;
pos[j] ++;
}
dp[i] = min(dp[pos[j] - ] + j * j, dp[i]);
}
}
printf("%lld", dp[n]);
return ;
}
Solution
二分性很明显，但是check竟然是用搜索回溯处理？？？真实震惊
搜索大概就是每次在剩下没有被覆盖的点中找到最靠左、最靠右、最靠下、最靠上四个极点位置，然后每次贪心往四个角（左上、左下、右上、右下）填矩阵，更新剩下没覆盖的点，搜三层回来即可.....
真的好玄学啊QAQ但是就是过了QAQ
Code
#include<bits/stdc++.h>
#define oo 0x3f3f3f3f
#define LL long long
using namespace std; int n, xmi, xma, ymi, yma, MA; struct Node {
LL x, y;
} tr[];
bool cmp1(Node a, Node b) { return a.x < b.x; }
bool cmp2(Node a, Node b) { return a.y < b.y; } bool flag, vis[];
LL now; void dfs(int dep, int tot) {
if(tot == n) { flag = ; return ; }
if(dep == ) return ;
bool used[] = {};
LL maxx = -oo, minx = oo, maxy = -oo, miny = oo;
for(int i = ; i <= n; i ++) {
if(vis[i]) continue;
maxx = max(maxx, tr[i].x); minx = min(minx, tr[i].x);
maxy = max(maxy, tr[i].y); miny = min(miny, tr[i].y);
} int cnt = ; LL xl = minx, xr = minx + now, yl = miny, yr = miny + now; cnt = ;
for(int i = ; i <= n; i ++) {
if(vis[i]) continue;
if(tr[i].x <= xr && tr[i].x >= xl && tr[i].y >= yl && tr[i].y <= yr) {
vis[i] = ; used[i] = ; cnt ++;
}
}
dfs(dep + , tot + cnt); if(flag) return ;
for(int i = ; i <= n; i ++) if(used[i]) vis[i] = used[i] = ; xl = minx, xr = minx + now, yl = maxy - now, yr = maxy; cnt = ;
for(int i = ; i <= n; i ++) {
if(vis[i]) continue;
if(tr[i].x <= xr && tr[i].x >= xl && tr[i].y >= yl && tr[i].y <= yr) {
vis[i] = ; used[i] = ; cnt ++;
}
}
dfs(dep + , tot + cnt); if(flag) return ;
for(int i = ; i <= n; i ++) if(used[i]) vis[i] = used[i] = ; xl = maxx - now, xr = maxx, yl = maxy - now, yr = maxy; cnt = ;
for(int i = ; i <= n; i ++) {
if(vis[i]) continue;
if(tr[i].x <= xr && tr[i].x >= xl && tr[i].y >= yl && tr[i].y <= yr) {
vis[i] = ; used[i] = ; cnt ++;
}
}
dfs(dep + , tot + cnt); if(flag) return ;
for(int i = ; i <= n; i ++) if(used[i]) vis[i] = used[i] = ; xl = maxx - now, xr = maxx, yl = miny, yr = miny + now; cnt = ;
for(int i = ; i <= n; i ++) {
if(vis[i]) continue;
if(tr[i].x <= xr && tr[i].x >= xl && tr[i].y >= yl && tr[i].y <= yr) {
vis[i] = ; used[i] = ; cnt ++;
}
}
dfs(dep + , tot + cnt); if(flag) return ;
for(int i = ; i <= n; i ++) if(used[i]) vis[i] = used[i] = ;
} bool check(LL mid) {
now = mid; flag = ;
for(int i = ; i <= n; i ++) vis[i] = ;
dfs(, );
return flag;
} LL erfen() {
LL l = , r = , ans;
while(l <= r) {
LL mid = (l + r) >> ;
if(check(mid)) ans = mid, r = mid - ;
else l = mid + ;
}
return ans;
} int main() {
freopen("cover.in", "r", stdin);
freopen("cover.out", "w", stdout);
scanf("%d", &n);
for(int i = ; i <= n; i ++)
scanf("%lld%lld", &tr[i].x, &tr[i].y);
LL ans = erfen();
printf("%lld", ans);
return ;
}
Solution
区间修改？？发现没那么简单QAQ，是求多个区间的和，没办法直接修改就快速求出答案。
所以推一推式子将$n^3$优化到$n^2$，要求的区间的区间和实际上可以由每条边的贡献算出来：$\sum_{i=L}^{R}{v[i]*(i-L+1)*(R-i+1)}$，此处$R$是事先$--$了的，因为$R-R+1$的边不能被算入贡献。
化简得$\sum{iv[i] * (L + R) - i^2v[i] + v[i] * (R - L * R + 1 - L)}$所以要维护的变量实际上只有$iv[i].i^2v[i].v[i]$三个的区间和即可，用一颗线段树结构体就好辣。
全都要开longlong才可以！！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std; LL n, m; LL gcd(LL a, LL b) {
return b == ? a : gcd(b, a % b);
} struct Node {
LL iv, v, iv2;
Node operator + (const Node &a) const {
Node c;
c.iv = iv + a.iv; c.v = v + a.v; c.iv2 = iv2 + a.iv2;
return c;
}
} TR[]; LL tag[], iv[], iv2[]; void push_down(LL nd, LL l, LL r) {
if(tag[nd]) {
LL d = tag[nd], mid = (l + r) >> ;
TR[nd << ].iv += d * (iv[mid] - iv[l - ]);
TR[nd << ].iv2 += d * (iv2[mid] - iv2[l - ]);
TR[nd << ].v += d * (mid - l + );
TR[nd << | ].iv += d * (iv[r] - iv[mid]);
TR[nd << | ].iv2 += d * (iv2[r] - iv2[mid]);
TR[nd << | ].v += d * (r - mid);
tag[nd << ] += d, tag[nd << | ] += d; tag[nd] = ;
}
} void update(LL nd) {
TR[nd] = TR[nd << ] + TR[nd << | ];
} void modify(LL nd, LL l, LL r, LL L, LL R, LL d) {
if(l >= L && r <= R) {
TR[nd].iv += d * (iv[r] - iv[l - ]);
TR[nd].iv2 += d * (iv2[r] - iv2[l - ]);
TR[nd].v += d * (r - l + );
tag[nd] += d;
return ;
}
push_down(nd, l, r); LL mid = (l + r) >> ;
if(L <= mid) modify(nd << , l, mid, L, R, d);
if(R > mid) modify(nd << | , mid + , r, L, R, d);
update(nd);
} Node query(LL nd, LL l, LL r, LL L, LL R) {
if(l >= L && r <= R) return TR[nd];
push_down(nd, l, r);
LL mid = (l + r) >> ; Node ans; ans.iv = ans.iv2 = ans.v = ;
if(L <= mid) ans = ans + query(nd << , l, mid, L, R);
if(R > mid) ans = ans + query(nd << | , mid + , r, L, R);
return ans;
} void init() {
for(LL i = ; i <= n; i ++) {
iv[i] = iv[i - ] + i;
iv2[i] = iv2[i - ] + i * i;
}
} int main() {
freopen("roadxw.in", "r", stdin);
freopen("roadxw.out", "w", stdout);
scanf("%lld%lld", &n, &m);
init();
for(LL t = ; t <= m; t ++) {
char s[]; LL L, R, V;
scanf("%s", s);
if(s[] == 'C') {
scanf("%lld%lld%lld", &L, &R, &V);
modify(, , n, L, R - , V);
} else {
scanf("%lld%lld", &L, &R);
R --;
Node a = query(, , n, L, R);
LL ans = a.iv * (L + R) - a.iv2 + a.v * (R - L * R + - L);
LL tot = R - L + ;
LL ans2 = tot * (tot - ) / ;
LL d = gcd(ans, ans2);
ans /= d, ans2 /= d;
printf("%lld/%lld\n", ans, ans2);
}
}
return ;
}