二分丶前缀和丶差分课件

二分

二分查找的 前提是在 有序的序列进行

普通的扫一遍的复杂度是 #card=math&code=%5Clarge%20O%28n%29&id=MUbU7) 而二分的复杂度是#card=math&code=%5Clarge%20O%28%20log%5En%29&id=A4lSz)

因为每次都将问题的规模缩小了一半

代表问题规模

一个二分十种写法!

1. 在单调递增的序列中 查找 数中最小的一个 即x的后继
2. 在单调递增的序列中 查找 数中最大的一个 即x的前驱

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<ctime>
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn];
int n;
int main(){
  cin >> n;
  for(int i = 1; i <= n; i++){
    cin >> a[i];
  }
  sort(a+1, a+1+n);
  int x;
  cin >> x;
  int l = 1;
  int r = n;
  while(l < r){ //  循环终止的时候  l = r   答案下标在  a[l]
    int mid = l +r >> 1;// 二进制下 右移一位  等于除二
    if(a[mid] >= x){
      r = mid;// check 成功     不加一  不减一
    } else{
      l = mid + 1;
    }
  }
  while(l < r){ //  循环终止的时候  l = r   答案下标在  a[l]
    int mid = (l +r + 1) >> 1;// 二进制下 右移一位  等于除二
    if(a[mid] <= x){
      l = mid;// check 成功     不加一  不减一
    } else{
      r = mid - 1;
    }
  }
  // int mid;
  // while(l <= r){
  //   mid = l + r >> 1;
  //   if(a[mid] >= x){
  //     r = mid - 1;
  //   } else{
  //     l = mid + 1;
  //   }
  // }
  cout << a[mid] << endl;
}

前缀和

#card=math&code=O%28n%29&id=v6yXg) 预处理 , #card=math&code=O%281%29&id=q5mMJ) 求出任意区间和

二维前缀和

画图 容斥一下即可

例题

给定一个长度为 的正整数序列, 求一个长度至少为的区间 使其区间平均值 最大

题解

-sum(l-1)%7D%7Br-l%2B1%7D%3Davg%0A#card=math&code=%5Clarge%20%5Cfrac%7Bsum%28r%29-sum%28l-1%29%7D%7Br-l%2B1%7D%3Davg%0A&id=IN2kB)

看到区间和, 联想到了最大子段和问题

最大子段和问题 同这个问题的答案并不能够直接转化 因为最大子段和与区间长度无关

我们在判定的时候也要略去 区间长度这一维 所以我们考虑二分 , 每个项都减去它, 判断序列长度大于 的最大子段和是否为负即可

for(int i = 1; i <= n; i++) {
    b[i] = a[i] - mid;  //  我们把每一项 都减去二分的平均数
}
for(int i = F; i <= n; i++){ //  因为区间长度要大于F  所有右端点 一定是在F  以后
    minn = min(minn, sum[i-F]);  //  维护一个  左端点的  最小值
    ans = max(ans, sum[i] - minn); // 和 备选答案 取个max
}

例题其二

给定 , 对于, #card=math&code=0%3C%3Dj%3C%3Dmin%28i%2Cm%29&id=IPh5c), 试问有多少对 满足,

题解

我们可以看到 每次询问都是 全局的一个子集 备选的pair都是连续的 我们可以考虑预处理出全部的答案

用 表示 题目输入为 时候的答案

%0A#card=math&code=%5Clarge%20sum%5Bi%5D%5Bj%5D%3Dsum%5Bi-1%5D%5Bj%5D%2Bsum%5Bi%5D%5Bj-1%5D-sum%5Bi-1%5D%5Bj-1%5D%2B%28k%7C%5Ctbinom%7Bi%7D%7Bj%7D%29%0A&id=ntbpY)

组合数用杨辉三角 递推一下就好

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define maxn 2001
int f[maxn][maxn];
int ans[maxn][maxn];
int n[10001];
int m[10001];
int sum[maxn][maxn];
int t,k;
int nm;
int mm;
int main()
{
        memset(ans,0,sizeof(ans));
    scanf("%d%d",&t,&k);
    for(int i=1;i<=t;i++)
    {
        scanf("%d%d",&n[i],&m[i]);
        nm=max(nm,n[i]);
        mm=max(mm,m[i]);
    }
    for(int i=1;i<=nm;i++)
    f[0][i]=1,f[i][i]=1;
    for(int i=2;i<=nm;i++)
        for(int j=1;j<=min(i,mm);j++)
    {
            f[j][i]=(f[j][i-1]+f[j-1][i-1])%k;

            if(f[j][i]==0)
               ans[j][i]=1;
    }

    memset(sum,0,sizeof(sum));
    for(int i=1;i<=nm;i++)
    {
        for(int j=1;j<=mm;j++)
        {
            sum[j][i]=sum[j][i-1]+sum[j-1][i]-sum[j-1][i-1]+ans[j][i];
    }

    }
    for(int p=1;p<=t;p++)
    {
        cout<<sum[m[p]][n[p]]<<endl;
    }
    return 0;

}

差分

定义差分数组

那么

意义：

#card=math&code=O%281%29&id=aw9vt) 处理区间加 例子：在 都加上5 等价于 同时

树上差分

将前缀和 转化为 子树和

将树上的链修改转化为#card=math&code=O%281%29&id=WY00i)点修改 例子: 统计点(边) 被访问的次数

点权差分

在点 到点 的路径上+1 （下同）

%5D—%EF%BC%8Cd%5Bfa%5Blca(u%2Cv)%5D%5D—%0A#card=math&code=%5Clarge%20d%5Bu%5D%2B%2B%2Cd%5Bv%5D%2B%2B%2Cd%5Blca%28u%2Cv%29%5D—%EF%BC%8Cd%5Bfa%5Blca%28u%2Cv%29%5D%5D—%0A&id=USYEb)

边权差分

%5D-%3D2%0A#card=math&code=%5Clarge%20d%5Bu%5D%2B%2B%2Cd%5Bv%5D%2B%2B%2Cd%5Blca%28u%2Cv%29%5D-%3D2%0A&id=t2bp4)

例题

给定你一棵 个节点的树， 通过每一条边权为 的边, 会有相应的时间代价, 与此同时你有 个任务, 每个任务指定树上两个点,

这个时候你可以把一条边的边权置位0, 所有任务同时开始, 试问完成的最短时间？

题解

最大值最小 显然考虑二分！！

如何判断一个时间是否能够合法, 我们先考虑吧大于 的 全部挑 出来, 这些需要全部再删掉一条边后满足

所以记录他们经过的边, 找到所有经过次数大于 的边, 判断将他改掉之后 是否能够满足答案

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn = 3e5 + 50;
#define ll long long
int read(){
  int x=0;
  int f=1;
  char ch=getchar();
  while(ch<'0'||ch>'9'){
    if(ch=='-')
    f=-1;
    ch=getchar();
  }
  while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';
    ch=getchar();
  }
  return x*f;
}
struct edge{
  int to, nxt , w;
} e[maxn << 1];
int cnt = 0;
int head[maxn];
int c[maxn]; // diff
void add(int u, int v, int w){
  e[++cnt].to = v;
  e[cnt].nxt = head[u];
  head[u] = cnt;
  e[cnt].w = w;
}
struct query {
  int x, y;
  int lca;
  ll dis = 0;
} q[maxn];
int dfn[maxn]; // dfs sequence of the tree
int tim = 0;
int L = 0;
int siz[maxn], top[maxn], fa[maxn], son[maxn], dep[maxn];
ll dis[maxn];
int dict[maxn]; // the length of the way to father
ll maxm;
int n, m;

void dfs1(int x){
  siz[x] = 1;
  for(int i = head[x]; i; i = e[i].nxt){
    int v = e[i].to;
    int w = e[i].w;
    if(v == fa[x])
    continue;
    fa[v] = x;
    dep[v] = dep[x] + 1;
    dis[v] = dis[x] + w;
    dict[v] = w;
    dfn[++tim] = v;
    dfs1(v);
    siz[x] += siz[v];
    if(!son[x] || siz[son[x]] < siz[v]){
      son[x] = v;
    }
  }
  return;
}
void dfs2(int x, int Top){
  top[x] = Top;
  if(son[x] > 0){
    dfs2(son[x], Top);
  }
  for(int i = head[x]; i; i = e[i].nxt){
    int v = e[i].to;
    if((v != fa[x]) && (v != son[x])){
      dfs2(v, v);
    }
  }
  return;
}
int Query(int x, int y){
  while(top[x] != top[y]){
    if(dep[top[x]] < dep[top[y]])
    swap(x, y);
    x = fa[top[x]];
  }
  return (dep[x] < dep[y]) ? x : y;
}
bool check(int x){
  int sum = 0;
  memset(c, 0, sizeof(c));
  for(int i = 1; i <= m; i++){
    if(q[i].dis <= x)
    continue;
    c[q[i].x]++;
    c[q[i].y]++;
    c[q[i].lca] -= 2;
    sum++; // count hom many querys is largr than the limitation
  }
  for(int i = n; i > 1; i--){
    c[fa[dfn[i]]] += c[dfn[i]];
    if(c[dfn[i]] >= sum && (maxm - dict[dfn[i]] <= x)){
      return true;
    }
  }
  return false;

}
int main(){
  n = read();
  m = read();
  for(int i = 1; i < n; i++){
    int x = read();
    int y = read();
    int w = read();
    L = max(L, w);
    add(x, y, w);
    add(y, x, w);
  }

  dep[1] = 1;
  fa[1] = 0; // ???
  dis[1] = 0;
  dfs1(1);
  dfs2(1, 1);
  // cout << " -----show the querys ----- " << endl;
  for(int i = 1; i <= m; i++){ // read the query ways on tree
    q[i].x = read();
    q[i].y = read();
    q[i].lca = Query(q[i].x, q[i].y);
    q[i].dis = dis[q[i].x] + dis[q[i].y] - 2 * dis[q[i].lca];
    // cout << q[i].lca << " " << q[i].dis << endl;
    maxm = max(maxm, q[i].dis);

  }
  ll l = maxm - L;
  ll r = maxm + 1;

  while(l < r) {
    ll mid = l + r >> 1;
    if(check(mid)) {
      // cout << "check successfully!   " << mid << endl; 
      r = mid;
    } else {
      // cout << "check failure : " << mid << endl;
      l = mid + 1;
    }
  }
  ll ans = l;
  printf("%lld\n", ans);


}