前缀和与差分

激光炸弹
预处理 使n^4 变成n^2
二位前缀和

#include <iostream>
using namespace std;
const int maxn = 5e3 + 5;
int sum[maxn][maxn];

int main(){
    int n, r;
    cin >> n >> r;
    for(int i = 1, x, y, c; i <= n; i++ ) {
        cin >> x >> y >> c;
        x ++ ,y ++;
        sum[x][y] += c;
    }
    for(int i = 1; i < maxn; i ++ ) 
        for(int j = 1; j < maxn ; j ++ ) 
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];

    int ans = 0;
    for(int i = r; i < maxn; i ++ ) for(int j = r; j < maxn; j ++ ) 
            ans = max(ans, sum[i][j] + sum[i - r][j - r] - sum[i - r][j] - sum[i][j - r]);
    cout << ans << endl;
    return 0;
}

IncDec序列
P22 一共3种有效改变序列的方法
有限正负抵消 只剩下 正数和负数的时候 让他和1 or n + 1 进行改变
这样 序列最后有 正数和P 负数asb和 Q ABS(P-Q) + 1 种情况
最少操作是 min(P, Q) + abs(P - Q);

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5 ;
int n, m;
int a[maxn], b[maxn];

int main() {
    cin >> n;
    ll x = 0, y = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(i == 1) b[1] = a[1];
        else {
            b[i] = a[i] - a[i - 1];
            if(b[i] > 0) x += b[i];
            else y -= b[i];
        }
    }
    cout << max(x, y) << endl << abs(x - y) + 1 << endl;
    return 0;
}

最高的牛
A可以看到B 意味A B之间的数据都小于他们

#include <iostream>
#include <map>
using namespace std;
typedef pair<int,int> P;
const int maxn = 100000 + 5 ;

int b[maxn];
map<P,bool> vis;

int main() {
    int n, i, h, R;
    cin >> n >> i >> h >> R;
    int x, y;
    for(int i = 1 ; i <= R ; i++) {
        cin >> x >> y;
        if(x > y) swap(x, y);
        if(vis[P(x,y)]) continue;
        vis[P(x,y)] = 1;
        b[x + 1]--, b[y] ++;
    }
    for(int i = 1 ; i<=n ; i++){
        b[i]+=b[i-1];
        cout << h + b[i] << endl;
    }
    return 0;
}

二分

整数域上的二分

  1. 当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
  2. 当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。
  3. 当我们要找的解集落在 l 到 mid 之间时选 1方法 ; 反之 选2方法

实数域上的二分
一般确定好eps 通常比要求 +2 即可
或者 for个100次什么的

ps 补充 后面的hash 找回文串 树状数组 找k大 最短路上的 k值路经过问题 都可以 转到二分判定上

三分求单峰函数极值 链接: https://blog.csdn.net/qq_40831340/article/details/90639163

最佳牛围栏
找一个长度大于L 连续的子段 同时这一段 平均数最大
1 首先有无长度现在的字段和最大问题 这个只要贪心一直加 加到<0 就清空重新加 找期间出现的最大值
2 子段长度不小于L 找他最大区段和
子段和可以变成前缀和减法的形式 这样 我们便可以 on的处理
同时 引入一个 生存周期 的变量 去存 sumr - suml r之前出现的最小 suml 这样就能 直接减到最小值 找到最大值
如此以来 我们可以考虑二分平均值 看看这个序列每一位 - 平均值能不能搞出来 整体大于0的数据
这样就有单调性了

#include <iostream>
using namespace std;

const int maxn = 1e5 + 5 ;
const double eps = 1e-6;

int n, L;

double a[maxn], b[maxn];
double sum[maxn];

bool chk(double mid) {
    for(int i = 1; i <= n; i++)
        b[i] = a[i] - mid;
    for(int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + b[i];

    double min_val = 1e10, ans = -1e10;

    for(int i = L ; i <= n; i++) {
        min_val = min(min_val, sum[i-L]);
        ans = max(ans, sum[i] - min_val);
    }
    return ans >= 0;
}

int main() {
    cin >> n >> L;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    double l = 0, r = 1e8;
    while(r-l>=eps) {
        double mid = (l + r) / 2;
        if(chk(mid))
            l = mid;
        else
            r = mid;
    }
    cout << (int)(r * 1000) << endl;
    return 0;
}

特殊排序
虽然是N^2 吧 题目要求不能cmp 超过1000次 所以二分找位置

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        res.push_back(1);
        for(int i=2;i<=N;i++){
            int l=0,r=res.size();
            while(l<r){
                int mid=(l+r)>>1;
                if(compare(res[mid],i)) l=mid+1;
                else r=mid;
            }
            res.push_back(i);
            for(int j=res.size()-1;j>l;j--) swap(res[j],res[j-1]);
        }
        return res;
    }
};