-
最近没什么时间更新了，今后更新频率会降低，但同时一次的内容也更多。
-
这个月的kickstart好可惜啊。。。
痛失35分。。其实就是太菜了。。。 -
开始在AcWing上打卡，逐步完成《算法竞赛进阶指南》的内容。
1. 重温扫描线写法
窗内的星星
#include<bits/stdc++.h>
using namespace std;
int n,W,H;
struct Line
{
int x,y1,y2,c;
bool operator<(const Line &b){
return x==b.x? x>b.c : x<b.x; //减掉c是在下一个x查询时起作用，因为假设矩形顶点都是整数，虽不影响答案，但实际上离真正的右边界还有些余量
}
}L[20005];
unordered_map<int,int> val;
int raw[40005];
struct SegmentTree{
int l,r;
int dat;
int add;
}t[20005*4];
void build(int l,int r,int p){
t[p].l=l,t[p].r=r;
t[p].dat=0;
if(l==r){
return ;
}
int mid= (l+r)>>1;
build(l,mid,p<<1);
build(mid+1,r,p<<1|1);
}
void spread(int x ){
if (t[x].add){
t[x*2].add+=t[x].add ;
t[2*x+1].add+=t[x].add;
t[x*2].dat+=t[x].add;
t[x*2+1].dat+=t[x].add;
t[x].add=0;
}
}
void change(int l,int r, int p,int x){
if (l<=t[p].l && t[p].r <=r) {
t[p].add +=x;
t[p].dat +=x;
return ;
}
spread(p);
int mid = (t[p].l+t[p].r)>>1;
if (l<=mid) change(l,r,p<<1,x) ;
if(mid<r) change(l,r,p<<1|1,x);
t[p].dat = max(t[p*2].dat,t[p*2+1].dat);
}
int main(){
while(~scanf("%d%d%d",&n,&W,&H)){
int tot=0,tot2=0;
memset(L,0,sizeof(L));
val.clear();
memset(raw,0,sizeof(raw));
for(int i=0;i<n;++i){
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
L[tot].x=x,L[tot].y1=y,L[tot].y2=y+H-1,L[tot++].c+=c;
L[tot].x=x+W-1,L[tot].y1=y,L[tot].y2=y+H-1,L[tot++].c-=c;
raw[tot2++]=y;
raw[tot2++]=y+H-1;
}
sort(L,L+tot);
sort(raw,raw+tot2);
int tot3 = unique(raw,raw+tot2)-raw;
for(int i=1;i<=tot3;++i){
val[raw[i-1]] = i;
}
build(1,tot3-1,1);
int ans =0;
for(int i =0;i<tot;++i){
change(val[L[i].y1],val[L[i].y2]-1,1,L[i].c);
ans = max(t[1].dat,ans);
}
printf("%d\n",ans);
}
return 0;
}
2. 学习了分块，“大段维护，局部朴素”思想。好像还混入了莫队算法这种奇妙的东西。。
（设分块数为T ，会发现要算法复杂度达到最优 ，可根据均值不等式得到T的值。)
蒲公英
#include <bits/stdc++.h>
using namespace std;
int a[40010];
int b[40010];
int cnt[40][40][40010], cnt_temp[40010];
int maxx[40][40];
int res[40][40];
int L[40], R[40];
int pos[40010];
int n, m, t;
int ask(int l, int r) {
int p = pos[l], q = pos[r];
int ans = 0;
int ret;
if (p == q) {
for (int i = l; i <= r; ++i) cnt_temp[a[i]] = 0;
for (int i = l; i <= r; ++i) {
cnt_temp[a[i]]++;
if (ans < cnt_temp[a[i]]) {
ret = a[i];
ans = cnt_temp[a[i]];
}
if (ans == cnt_temp[a[i]] && a[i] < ret) {
ret = a[i];
}
}
return b[ret];
} else {
ans = maxx[p + 1][q - 1];
ret = res[p + 1][q - 1];
for (int i = l; i <= R[p]; ++i) {
cnt_temp[a[i]] = 0;
}
for (int i = L[q]; i <= r; ++i) {
cnt_temp[a[i]] = 0;
}
for (int i = l; i <= R[p]; ++i) {
cnt_temp[a[i]]++;
if (ans < cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]]) {
ret = a[i];
ans = cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]];
}
if (ans == cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]] && a[i] < ret) {
ret = a[i];
}
}
for (int i = L[q]; i <= r; ++i) {
cnt_temp[a[i]]++;
if (ans < cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]]) {
ret = a[i];
ans = cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]];
}
if (ans == cnt_temp[a[i]] + cnt[p + 1][q - 1][a[i]] && a[i] < ret) {
ret = a[i];
}
}
return b[ret];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
b[i] = a[i];
}
t = pow(1.0 * n, 1.0 / 3.0);
for (int i = 1; i <= t; ++i) {
L[i] = (i - 1) * (n / t) + 1;
R[i] = n / t * i;
}
if (R[t] < n) t++, L[t] = R[t - 1] + 1, R[t] = n;
sort(b + 1, b + n + 1);
int M = unique(b + 1, b + 1 + n) - b - 1;
for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + 1 + M, a[i]) - b;
int T = 1;
for (int i = 1; i <= n; ++i) {
pos[i] = T;
if (i >= R[T]) T++;
}
for (int i = 1; i <= t; ++i) {
for (int j = i; j <= t; ++j) {
for (int k = L[i]; k <= R[j]; ++k) {
cnt[i][j][a[k]]++;
if (maxx[i][j] < cnt[i][j][a[k]]) {
maxx[i][j] = cnt[i][j][a[k]];
res[i][j] = a[k];
}
if (maxx[i][j] == cnt[i][j][a[k]] && a[k] < res[i][j]) {
res[i][j] = a[k];
}
}
}
}
int x = 0;
int l0, r0, l, r;
while (m--) {
scanf("%d%d", &l0, &r0);
l = (l0 + x - 1) % n + 1;
r = (r0 + x - 1) % n + 1;
if (l > r) swap(l, r);
printf("%d\n", x = ask(l, r));
}
return 0;
}还有做法是保存段边界为端点的区间众数。这个做法涉及到一个技巧，就是顺序保存数a在序列里的出现位置，然后对要求范围的L,R进行二分查找，下标相减可得到a在[L,R]中的出现次数。
磁力块
#include<bits/stdc++.h>
using namespace std;
int x0,Y0,pl;
long long rl;
int N;
struct stone{
int m,cp;
long long r;
long long cr;
bool operator<(stone a){
return m<a.m;
}
}A[250050];
bool cmp(stone a,stone b){
return a.r<b.r;
}
int L[505];
int R[505];
int maxx[505];
int v[250050];
int main(){
scanf("%d%d%d%lld%d",&x0,&Y0,&pl,&rl,&N);
A[0].r=0;
A[0].cr=rl*rl;
A[0].cp=pl;
A[0].m=-1;
for(int i=1;i<=N;++i){
int x,y,m,p;
long long r;
scanf("%d%d%d%d%lld",&x,&y,&m,&p,&r);
A[i].r=(long long)(x-x0)*(x-x0)+(long long)(y-Y0)*(y-Y0);
A[i].m=m;
A[i].cr=r*r;
A[i].cp=p;
}
sort(A+1,A+1+N);
int t =sqrt(N);
for(int i=1;i<=t;++i){
L[i]=(i-1)*(N/t)+1;
R[i]=i*(N/t);
maxx[i]=A[R[i]].m;
}
if(R[t]<N) t++,L[t]=R[t-1]+1,R[t]=N,maxx[t]=A[N].m;
for(int i=1;i<=t;++i){
sort(A+L[i],A+R[i]+1,cmp);
}
int ans=0;
queue<stone> q;
q.push(A[0]);
v[0]=1;
while(q.size()){
stone S = q.front();
q.pop();
for(int i=1;i<=t;++i){
if(maxx[i]<=S.cp){
while(L[i]<=R[i] && A[L[i]].r<=S.cr){
if (!v[L[i]]){
q.push(A[L[i]]);
v[L[i]]=1;
ans++;
}
L[i]++;
}
}
else {
for(int j = L[i];j<=R[i];++j){
if(!v[j] && A[j].m<=S.cp && A[j].r<=S.cr){
q.push(A[j]);
v[j]=1;
ans++;
}
}
break;
}
}
}
printf("%d\n",ans);
return 0;
}小Z的袜子
莫队离线处理，将询问区间排序、分块，由已经求出的区间推至相邻的区间。
#include <bits/stdc++.h>
using namespace std;
struct query {
int l, r, id, pos;
long long ans, base;
bool operator<(const query& a) { return l < a.l; }
} Q[50005];
int L[50005];
int R[50005];
int num[50005];
int N, M;
int C[50005];
bool cmp(query a, query b) {
if (a.pos == b.pos) {
return a.r < b.r;
} else
return a.pos < b.pos;
}
bool cmp2(query a, query b) { return a.id < b.id; }
int main() {
scanf("%d%d", &N, &M);
for (int i = 1; i <= N; ++i) {
scanf("%d", &C[i]);
}
int t = sqrt(N);
int T = 0;
for (int i = 1; i <= M; ++i) {
int il, ir;
scanf("%d%d", &il, &ir);
Q[i].l = il, Q[i].r = ir;
Q[i].id = i;
Q[i].pos = il / t + 1;
T = max(T, Q[i].pos);
}
sort(Q + 1, Q + 1 + M, cmp);
int p = 0;
for (int i = 1; i <= M; ++i) {
if (Q[i].pos != p) {
L[++p] = i;
if (p > 0) R[p - 1] = i - 1;
}
}
R[p] = M;
long long temp, bans;
for (int i = 1; i <= T; ++i) {
memset(num, 0, sizeof(num));
int first = L[i];
int l = Q[first].l, r = Q[first].r;
for (int j = l; j <= r; ++j) {
Q[first].ans -= (long long)num[C[j]] * (num[C[j]] - 1) / 2;
num[C[j]]++;
Q[first].ans += (long long)num[C[j]] * (num[C[j]] - 1) / 2;
}
temp = (long long)(r - l + 1) * (r - l) / 2;
bans = Q[first].ans;
if (Q[first].ans == 0) {
Q[first].base = 1;
} else if (bans > temp) {
Q[first].base = 1, Q[first].ans = 1;
} else {
Q[first].ans = bans / __gcd(bans, temp);
Q[first].base = temp / __gcd(bans, temp);
}
for (int j = L[i] + 1; j <= R[i]; ++j) {
int l = Q[j].l, r = Q[j].r;
Q[j].ans = bans;
if (Q[j - 1].l > l) {
for (int k = l; k < Q[j - 1].l; ++k) {
Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
num[C[k]]++;
Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
}
} else if (Q[j - 1].l < l) {
for (int k = Q[j - 1].l; k < l; ++k) {
Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
num[C[k]]--;
Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
}
}
for (int k = Q[j - 1].r + 1; k <= r; ++k) {
Q[j].ans -= (long long)num[C[k]] * (num[C[k]] - 1) / 2;
num[C[k]]++;
Q[j].ans += (long long)num[C[k]] * (num[C[k]] - 1) / 2;
}
temp = (long long)(r - l + 1) * (r - l) / 2;
bans = Q[j].ans;
if (Q[j].ans == 0) {
Q[j].base = 1;
} else if (bans > temp) {
Q[j].ans = Q[j].base = 1;
} else {
Q[j].ans = bans / __gcd(bans, temp);
Q[j].base = temp / __gcd(bans, temp);
}
}
}
sort(Q + 1, Q + 1 + M, cmp2);
for (int i = 1; i <= M; ++i) {
printf("%lld/%lld\n", Q[i].ans, Q[i].base);
}
return 0;
}3.学习了点分治，也就是树上的分治，相比于线性数组里的序列[L,R]，树对应的是两点之间的路径，线性序列二分对应于找树的重心。此题在递归求解时，当前层的需求是得到两点路径经过树根p的情况，考虑到会遍历整棵树，两点在同一棵p的子树（不经过p）的情况也会被包括，但是路径长度却算上了子树树根到父结点p的距离，要减掉这种情况（容斥）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 40000+100;
struct edge{
int to,w;
};
int N,K;
int vis[maxn];
int max_part[maxn];
int _size[maxn];
int d[maxn];
int b[maxn];
int len[maxn];
int root;
int tot_node;
int ans;
vector<edge> E[maxn*2];
void addEdge(int x,int y,int z){
E[x].push_back(edge{y,z});
}
void getRoot(int u,int fa){
max_part[u] = 0;
_size[u]=1;
for(int i = 0;i<E[u].size();++i){
int v =E[u][i].to;
if(vis[v]|| v ==fa) continue;
getRoot(v,u);
_size[u] += _size[v];
max_part[u]=max(max_part[u],_size[v]);
}
max_part[u] = max(max_part[u],tot_node - _size[u]);
if (max_part[u] < max_part[root]){
root =u;
}
}
void getDis(int u,int fa){
len[++len[0]] = d[u];
for(int i=0;i<E[u].size();++i){
int v = E[u][i].to;
if(vis[v] || v == fa ) continue;
d[v] = d[u]+E[u][i].w;
getDis(v,u);
}
}
int cal(int u,int now){
d[u] = now , len[0]=0;
getDis(u,0);
sort(len+1,len+len[0]+1);
int all = 0;
for(int l=1,r=len[0];l<r;){
if(len[l]+len[r]<=K){
all+=r-l;
++l;
}
else r--;
}
return all;
}
void solve(int u){
vis[u] = true;
ans +=cal(u,0);
for(int i=0;i<E[u].size();++i){
int v = E[u][i].to;
if(vis[v] ) continue;
ans -= cal(v, E[u][i].w);
tot_node = _size[v];
root =0;
getRoot(v,u);
solve(root);
}
}
int main(){
while(~scanf("%d%d",&N,&K) && N && K){
for(int i=1;i<=N;++i){
E[i].clear();
}
ans = 0;
memset(vis,0,sizeof(vis));
for(int i=1;i<N;++i){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
addEdge(x+1,y+1,z);
addEdge(y+1,x+1,z);
}
tot_node = N;
max_part[0]=N;
root = 0;
getRoot(1,0);
solve(root);
printf("%d\n",ans);
}
return 0;
}