• 最近没什么时间更新了，今后打算一个月更一次。

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

对延迟标记要有深入的理解。。。多个标记同时存在时要考虑顺序

参考：http://www.cfzhao.com/2019/04/03/hdu-4578-transformation/

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int SIZE = 100005;
const int MOD = 10007;
int n, q;

struct SegmentTree {
  int l, r;
  int sum,sum2,sum3;
  int lazy_add,lazy_mul,lazy_assign;
 #define l(x) tree[x].l
 #define r(x) tree[x].r
 #define sum(x) tree[x].sum
 #define sum2(x) tree[x].sum2
 #define sum3(x) tree[x].sum3
 #define lazy_add(x) tree[x].lazy_add
 #define lazy_mul(x) tree[x].lazy_mul
 #define lazy_assign(x) tree[x].lazy_assign
} tree[SIZE * 4];

void pushup(int p){
  sum(p)=(sum(p<<1|1)+sum(p<<1))%MOD;
  sum2(p)=(sum2(p<<1|1)+sum2(p<<1))%MOD;
  sum3(p)=(sum3(p<<1|1)+sum3(p<<1))%MOD;
}

void spread(int p){
  if(lazy_assign(p)){
    int s1=lazy_assign(p)%MOD,s2=s1*lazy_assign(p)%MOD,s3=s2*lazy_assign(p)%MOD;
    sum(p<<1|1)=s1*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum(p<<1)=s1*(r(p<<1)-l(p<<1)+1)%MOD;
    sum2(p<<1|1)=s2*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum2(p<<1)=s2*(r(p<<1)-l(p<<1)+1)%MOD;
    sum3(p<<1|1)=s3*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum3(p<<1)=s3*(r(p<<1)-l(p<<1)+1)%MOD;
    lazy_assign(p<<1|1)=lazy_assign(p<<1)=lazy_assign(p);
    lazy_add(p<<1|1)=lazy_add(p<<1)=0;
    lazy_mul(p<<1|1)=lazy_mul(p<<1)=1;
    lazy_assign(p)=0; 
  }
  if(lazy_mul(p)!=1){
    int s1=lazy_mul(p)%MOD,s2=s1*lazy_mul(p)%MOD,s3=s2*lazy_mul(p)%MOD;
    sum(p<<1|1)=sum(p<<1|1)*s1%MOD;
    sum(p<<1)=sum(p<<1)*s1%MOD;
    sum2(p<<1|1)=sum2(p<<1|1)*s2%MOD;
    sum2(p<<1)=sum2(p<<1)*s2%MOD;
    sum3(p<<1|1)=sum3(p<<1|1)*s3%MOD;
    sum3(p<<1)=sum3(p<<1)*s3%MOD;
    lazy_mul(p<<1|1)=lazy_mul(p<<1|1)*lazy_mul(p)%MOD;
    lazy_mul(p<<1)=lazy_mul(p<<1)*lazy_mul(p)%MOD;
    lazy_add(p<<1|1)=lazy_add(p<<1|1)*lazy_mul(p)%MOD;
    lazy_add(p<<1)=lazy_add(p<<1)*lazy_mul(p)%MOD;
    lazy_mul(p)=1;
  }
  if(lazy_add(p)!=0){
    int s1=lazy_add(p)%MOD,s2=s1*lazy_add(p)%MOD,s3=s2*lazy_add(p)%MOD;
    sum3(p<<1|1)=(sum3(p<<1|1)+3*s1%MOD*sum2(p<<1|1)%MOD+3*s2%MOD*sum(p<<1|1)%MOD+s3*(r(p<<1|1)-l(p<<1|1)+1)%MOD)%MOD;
    sum3(p<<1)=(sum3(p<<1)+3*s1%MOD*sum2(p<<1)%MOD+3*s2%MOD*sum(p<<1)%MOD+s3*(r(p<<1)-l(p<<1)+1)%MOD)%MOD;
    sum2(p<<1|1)=(sum2(p<<1|1)+2*s1%MOD*sum(p<<1|1)%MOD+s2*(r(p<<1|1)-l(p<<1|1)+1)%MOD)%MOD;
    sum2(p<<1)=(sum2(p<<1)+2*s1%MOD*sum(p<<1)%MOD+s2*(r(p<<1)-l(p<<1)+1)%MOD)%MOD;
    sum(p<<1|1)=sum(p<<1|1)+lazy_add(p)*(r(p<<1|1)-l(p<<1|1)+1)%MOD;
    sum(p<<1)=sum(p<<1)+lazy_add(p)*(r(p<<1)-l(p<<1)+1)%MOD;
    lazy_add(p<<1|1)=(lazy_add(p<<1|1)+lazy_add(p))%MOD;
    lazy_add(p<<1)=(lazy_add(p<<1)+lazy_add(p))%MOD;
    lazy_add(p)=0;
  }

}

void build(int p, int l, int r) {
  l(p) = l, r(p) = r;
  lazy_add(p)=0,lazy_assign(p)=0,lazy_mul(p)=1;
  if (l == r) {
    sum(p)=sum2(p)=sum3(p)=0;
    return ;
  }
  int mid = (l + r) >>1;
  build(p<<1, l, mid);
  build(p <<1 | 1, mid + 1, r);
  pushup(p);
}

void change(int p, int L,int R, int c,int d) {
  if(L<=l(p) && r(p)<=R){
    ll s1=d%MOD,s2=s1*d%MOD,s3=s2*d%MOD;
    if(c==1){
     sum3(p)=(sum3(p)+3*s1%MOD*sum2(p)%MOD+3*s2%MOD*sum(p)%MOD+s3*(r(p)-l(p)+1)%MOD)%MOD;
     sum2(p)=(sum2(p)+2*s1%MOD*sum(p)%MOD+s2*(r(p)-l(p)+1)%MOD)%MOD;
     sum(p)=(sum(p)+s1*(r(p)-l(p)+1)%MOD)%MOD;
     lazy_add(p)=(lazy_add(p)+d)%MOD;
    }
    if(c==2){
      sum(p)=s1*sum(p)%MOD;
      sum2(p)=s2*sum2(p)%MOD;
      sum3(p)=s3*sum3(p)%MOD;
      lazy_mul(p)=lazy_mul(p)*d%MOD;
      lazy_add(p)=lazy_add(p)*d%MOD;
    }
    if(c==3){
      sum(p)=s1*(r(p)-l(p)+1)%MOD;
      sum2(p)=s2*(r(p)-l(p)+1)%MOD;
      sum3(p)=s3*(r(p)-l(p)+1)%MOD;
      lazy_assign(p)=d;
      lazy_add(p)=0;
      lazy_mul(p)=1;
    }
    return;
  } 
  spread(p);
  int mid=(l(p)+r(p))>>1;
  if(L<=mid) change(p<<1,L,R,c,d);
  if(R>mid) change(p<<1|1,L,R,c,d);
  pushup(p);
} 

int ask(int p,int l,int r,int c){
    if(l<=l(p) && r(p)<=r){
      if(c==1) return sum(p);
      if(c==2) return sum2(p);
      if(c==3) return sum3(p);
    }
    spread(p);
    int mid=(l(p)+r(p))>>1;
    int val=0;
    if(l<=mid)  val+=ask(p<<1,l,r,c);
    if(r>mid)  val+=ask(p<<1|1,l,r,c);
    return val%MOD;
} 

int main() {
  int T,kase=0;
  while(~scanf("%d%d",&n,&q)&&n&&q){
    build(1,1,n);
    while(q--){
      int a,x,y,c;
      scanf("%d%d%d%d",&a,&x,&y,&c);
      if(a!=4) change(1,x,y,a,c);
      else{
        printf("%d\n",ask(1,x,y,c));
      }
    }

  }
  return 0;
}

在平面坐标系里给出一些矩形,求面积并.
Atlantis

#include<cstdio>
#include<map>
#include<algorithm>
#include<iostream>
using namespace std;

const int N=106;
int n,m,num=0;

struct P{
    double x,y,z;
    int k;
    bool operator<(const P w) const{
        return x<w.x;
    }
}a[N<<1];

double raw[N<<1];
map<double ,int > val ;

struct Tree{
    int l,r,cnt;
    double len;
}t[N<<3];

void build(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    t[p].cnt=0;
    t[p].len=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}

void change(int p,int l,int r,int k){
    if(l<=t[p].l&&r>=t[p].r) t[p].len=((t[p].cnt+=k)>0?raw[t[p].r+1]-raw[t[p].l]:0);
    if(t[p].l==t[p].r) return;
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid) change(p<<1,l,r,k);
    if(r>mid) change(p<<1|1,l,r,k);
    t[p].len=(t[p].cnt>0?raw[t[p].r+1]-raw[t[p].l]:t[p<<1].len+t[p<<1|1].len);
}

void  Atlantis(){
    for(int i=1;i<=n;++i){
        int k=i<<1;
        double y,z; //竖直方向坐标
        scanf("%lf %lf %lf %lf",&a[k-1].x,&y,&a[k].x,&z);
        raw[k-1]=a[k-1].y=a[k].y=y;//矩形左边界
        raw[k]=a[k-1].z=a[k].z=z; //矩形右边界
        a[k-1].k=1;
        a[k].k=-1;
    }
    n<<=1;
    //离散化
    sort(raw+1,raw+n+1);
    int m=unique(raw+1,raw+n+1)-(raw+1);
    for(int i=1;i<=m;++i) val[raw[i]]=i;
    sort(a+1,a+n+1);
    build(1,1,m-1);
    double ans=0;
    for(int i=1;i<n;++i){
        int y=val[a[i].y],z=val[a[i].z]-1;  // y:[val[a[i].y], val[a[i].y]+1]  z: [val[a[i].z]-1, val[a[i].z]]
        change(1,y,z,a[i].k); //y~z: [val[a[i].y], val[a[i].z]
        ans+=t[1].len*(a[i+1].x-a[i].x); //t[1].len 整个扫描线覆盖的长度
    }
    printf("Test case #%d\nTotal explored area: %.2f\n\n", ++num, ans);
}

int main() {
    while (cin >> n && n) Atlantis();
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZE = 100010;

struct SegmentTree{
    int l,r;
    long long sum,add;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define sum(x) tree[x].sum
    #define add(x) tree[x].add
} tree[SIZE*4];

int a[SIZE],n,m;

void build(int p,int l,int r){
    l(p)=l,r(p)=r;
    if(l==r) { sum(p)=a[l];return; }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    sum(p)=sum(p*2)+sum(p*2+1);
}

void spread(int p){
    if(add(p)){
        sum(p*2)+=add(p)*(r(p*2)-l(p*2)+1);
        sum(p*2+1)+=add(p)*(r(p*2+1)-l(p*2+1)+1);
        add(p*2)+=add(p);
        add(p*2+1)+=add(p);
        add(p)=0;
    }
}

void change(int p,int l,int r,int d){
    if(l<=l(p) && r>=r(p)){
        sum(p)+=(long long) d*(r(p)-l(p)+1);
        add(p)+=d;
        return;
    }
    spread(p);
    int mid=(l(p)+r(p))/2;
    if(l<=mid) change(p*2,l,r,d);
    if(r>mid) change(p*2+1,l,r,d);
    sum(p)=sum(p*2)+sum(p*2+1);
}

long long ask(int p,int l,int r){
    if(l<=l(p) && r>=r(p)) return sum(p);
    spread(p);
    int mid=(l(p)+r(p))/2;
    long long val=0;
    if(l<=mid) val+=ask(p*2,l,r);
    if(r>mid) val+=ask(p*2+1,l,r);
    return val;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--){
        char op[2];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='C'){
            scanf("%d",&d);
            change(1,l,r,d);
        }
        else printf("%lld\n",ask(1,l,r));
    }
    return 0;
}

RT,线段树单点修改,区间查询.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int maxn = 1e6;

#define SIZE 500000

int a[SIZE+1];
struct SegmentTree {
    int l,r;
    int dat,sum,lmax,rmax;
    SegmentTree() {
        l = r = sum = 0;
        lmax = rmax  =dat= -INF;
    }
} t[SIZE*4];

void build(int p,int l,int r) {
    t[p].l=l,t[p].r=r;
    if(l==r) {
        t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(p*2,l,mid);
    build(p*2+1,mid+1,r);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

void change(int p,int x,int v) {
    if(t[p].l==t[p].r) {
        t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=v;
        return;
    }
    int mid=(t[p].l+t[p].r)/2;
    if(x<=mid)
        change(p*2,x,v);
    else
        change(p*2+1,x,v);
    t[p].dat=max(max(t[p*2].dat,t[p*2+1].dat),t[p*2].rmax+t[p*2+1].lmax);
    t[p].lmax=max(t[p*2].lmax,t[p*2].sum+t[p*2+1].lmax);
    t[p].rmax=max(t[p*2+1].rmax,t[p*2+1].sum+t[p*2].rmax);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}

SegmentTree ask(int p,int l,int r) {
    if(l<=t[p].l&&r>=t[p].r) {
        return t[p];
    }
    SegmentTree res,a,b;
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) {
        a=ask(p*2,l,r);
        res.sum+=a.sum;
    }
    if(r>mid) {
        b=ask(p*2+1,l,r);
        res.sum+=b.sum;
    }
    res.lmax=max(a.lmax,a.sum+b.lmax);
    res.rmax=max(b.rmax,b.sum+a.rmax);
    res.dat=max(max(a.dat,b.dat),a.rmax+b.lmax);
    return res;
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        scanf("%d",&a[i]);
    }
    build(1,1,n);
    while(m--) {
        int k,x,y;
        scanf("%d%d%d",&k,&x,&y);
        if(k==1) {
            if(x>y)
                swap(x,y);
            printf("%d\n",ask(1,x,y).dat);
        } else {
            change(1,x,y);
        }
    }
    return 0;
}

题目链接:CH4201

对某个点,求前面和后面分别有多少个点的纵坐标是比它大的,两数相乘就是以该点为中间点,能构成的"v"的数量.

"^"同理.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

#define maxn 200005

typedef long long ll;
typedef unsigned long long ull;

int c[maxn];
int a[maxn];
int Right1[maxn];
int Left1[maxn];
int Right2[maxn];
int Left2[maxn];
int n;

int ask(int x){
  int ans=0;
  for(;x;x-=x&-x) ans+=c[x];
  return ans;
}

void add(int x,int y){
  for(;x<=n;x+=x&-x) c[x]+=y;
}

int main() {
  cin>>n;
  for(int i=1;i<=n;++i){
    cin>>a[i];
  }
  for(int i=n;i>0;--i){
      Right1[i]=n-i-ask(a[i]);
      Right2[i]=ask(a[i]-1);
      add(a[i],1);
  }
  memset(c,0,sizeof(c));
  for(int i=1;i<=n;++i){
    Left1[i]=i-1-ask(a[i]);
    Left2[i]=ask(a[i]-1);
    add(a[i],1);
  }
  ll ans1=0,ans2=0;

  for(int i=1;i<=n;++i){
    ans1+=(ll)Left1[i]*Right1[i];
    ans2+=(ll)Left2[i]*Right2[i];
  } 
  cout<<ans1<<" "<<ans2<<endl;
  return 0;
}

题目链接:BZOJ 4195

在数据范围大,但实际数据个数不大的时候,采用离散化避免超出数组空间.

code:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

#define maxn 1000005

typedef long long ll;
typedef unsigned long long ull;

int fa[maxn * 2];

int x1[maxn];
int x2[maxn];
int s[maxn];
int n;
vector<int> b;

void init() {
  b.clear();
  for (int i = 0; i <= 2 * n; ++i) {
    fa[i] = i;
  }
}

int get(int x) {
  if (x == fa[x]) return x;
  return fa[x] = get(fa[x]);
}

void merge(int x, int y) { fa[get(x)] = get(y); }

void discrete() {
  sort(b.begin(), b.end());
  unique(b.begin(), b.end());
}
int query(int x) { return lower_bound(b.begin(), b.end(), x) - b.begin(); }

int main() {
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    init();
    for (int k = 1; k <= n; ++k) {
      cin >> x1[k] >> x2[k] >> s[k];
      b.push_back(x1[k]);
      b.push_back(x2[k]);
    }
    discrete();
    for (int i = 1; i <= n; ++i) {
      if (s[i]) {
        int x = query(x1[i]);
        int y = query(x2[i]);
        merge(x, y);
      }
    }
    int flag = 0;
    for (int i = 1; i <= n; ++i) {
      if (!s[i]) {
        int x = query(x1[i]);
        int y = query(x2[i]);
        if (get(x) == get(y)) {
          cout << "NO" << endl;
          flag = 1;
          break;
        }
      }
    }
    if (!flag) {
      cout << "YES" << endl;
    }
  }
  return 0;
}