• 最近没什么时间更新了，今后更新频率会降低，但同时一次的内容也更多。

• 这个月的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;
}