描述：n个试管，给你每个试管装有的水的高度，q次询问，1）把一个试管的水量改成x，2）假设你可以选择任意的一些试管，一共添加v高度的水，问添加了水的这些试管，添加水后的最大高度的最小值。

最小化最大值，首先想二分答案，假设添加水后的最大高度为d，再看d能不能达到。
水柱高度小于d的试管数量记为cnt，水总和为sum。
可以往这些试管中加的水量：v1=d*cnt-sum，若v1>=v，则d或许可以更小，否则这些试管加不了v高度的水，加完后高度就大于d，所以d要往上调。

现在问题变成了如何动态维护cnt和sum的问题，这用线段树很容易做到。
首先将用到的所有高度离散化，线段树区间是高度区间，然后就可以愉快维护某个高度区间的cnt和sum了。

单点修改logn；二分logn，每次检查：先二分离散化的后高度的位置logn，查询cnt和sum logn => log2n。总的时间复杂度 qlog2n。

其实这用树状数组也可以做到。用一个数组b维护每个高度的cnt，用一个数组c维护每个高度的sum。因为这只涉及到单点修改和区间和。

#include<bits/stdc++.h>

using namespace std;

#define eps 1e-5
#define x first
#define y second

const int N=1e5+10,M=2*N;

typedef long long ll;
typedef pair<ll,ll> pll;

int n,q;
int h[N];
struct node{
    int op;
    ll a;
    int b;

}input[N];

struct node2{
    ll cnt,sum;
}tr[M<<2];

vector<int> alls;

int find(int x){
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

void modify(int p, int l,int r,int i,int x,int y){
    if(l==r){
        tr[p].cnt+=x;
        tr[p].sum+=y;
        return;
    }
    int mid=(l+r)>>1;

    if(i<=mid) modify(p*2,l,mid,i,x,y);
    else modify(p*2+1,mid+1,r,i,x,y);
    tr[p].cnt=tr[p*2].cnt+tr[p*2+1].cnt;
    tr[p].sum=tr[p*2].sum+tr[p*2+1].sum;
}

pll ask(int p,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return {tr[p].cnt,tr[p].sum};
    }
    int mid=(l+r)>>1;
    ll cnt=0,sum=0;
    if(L<=mid) {
        auto t=ask(p*2,l,mid,L,R);
        cnt+=t.x;
        sum+=t.y;
    }
    if(R>=mid+1){
        auto t=ask(p*2+1,mid+1,r,L,R);
        cnt+=t.x;
        sum+=t.y;
    }

    return {cnt,sum};
}

bool check(double x,ll v){
    int d=x>alls.back()?alls.back():x;
    int i=find(d);
    auto t=ask(1,0,alls.size()-1,0,i);
    double v1=x*t.x-t.y;
    if(v1>=v) return true;
    return false;
}

int main(){
    scanf("%d%d",&n,&q);

    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
        alls.push_back(h[i]);
    }

    for(int i=0;i<q;i++){
        int op;
        scanf("%d",&op);
        if(op==1){
            ll a;
            int b;
            scanf("%lld%d",&a,&b);
            input[i]={op,a,b};
            alls.push_back(b);
        }
        else{
            ll a;
            scanf("%lld",&a);
            input[i]={op,a,0};
        }
    }

    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(int i=1;i<=n;i++){
        int j=find(h[i]);
        modify(1,0,alls.size()-1,j,1,h[i]);
    }

    for(int i=0;i<q;i++){
        auto u=input[i];
        if(u.op==1){
            int j=find(h[u.a]);
            modify(1,0,alls.size()-1,j,-1,-h[u.a]);
            h[u.a]=u.b;
            j=find(u.b);
            modify(1,0,alls.size()-1,j,1,u.b);
        }
        else{
            double lb=0,ub=1e24+10;
            while(ub-lb>=eps){
                double mid=(lb+ub)/2;
                check(mid,u.a)?ub=mid:lb=mid;
            }
            printf("%.5lf\n",ub);
        }
    }

    return 0;
}

#include<cstdio>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=10005,M=4*N;

int n;
struct node{
    int l,r; 
}in[N];
vector<int > alls;
bool st[N];

int ans;

int lz[M<<2];

int find(int x){
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin(); 
}

void modify(int p,int l,int r,int L,int R,int id){
    if(L<=l&&R>=r){
        lz[p]=id;
        return;
    }

    if(lz[p]!=-1){
        lz[p<<1]=lz[p<<1|1]=lz[p];
        lz[p]=-1;
    }

    int mid=(l+r)>>1;
    if(L<=mid) modify(p<<1,l,mid,L,R,id);
    if(R>mid) modify(p<<1|1,mid+1,r,L,R,id);
} 

int dfs(int p,int l,int r){
    if(lz[p]!=-1){
        if(!st[lz[p]]){
            st[lz[p]]=true;
            return 1;
        }
        else return 0;
    }
    if(l==r) return 0;
    int mid=(l+r)>>1;
    return dfs(p<<1,l,mid) + dfs(p<<1|1,mid+1,r);  
}

int main(){

    int t;
    scanf("%d",&t);

    while(t--){
        alls.clear();
        ans=0;
        memset(st,false,sizeof st);
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            int l,r;
            scanf("%d%d",&l,&r);
            in[i]={l,r};
            alls.push_back(l);
            alls.push_back(r);
            alls.push_back(r+1);
        }

        sort(alls.begin(),alls.end());
        alls.erase(unique(alls.begin(),alls.end()),alls.end());

        memset(lz,-1,sizeof lz);

        for(int i=0;i<n;i++){
            int l=find(in[i].l), r=find(in[i].r);
            modify(1,0,alls.size()-1,l,r,i);
        }

        printf("%d\n",dfs(1,0,alls.size()-1););
    }

    return 0;
}

#include<iostream>
#include<bitset>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=1e5+10,M=2*N,T=31;

int n,m,q;
bitset<T> ans[M<<2];
int lz[M<<2];

inline void make_tag(int p,int color){
    lz[p]=color;
    ans[p].reset();
    ans[p].set(color-1,1);
}

void down(int p){
    if(lz[p]){
        make_tag(p<<1,lz[p]), make_tag(p<<1|1,lz[p]);
        lz[p]=0;
    }
}

void modify(int p,int l,int r,int L,int R,int color){
    if(L<=l&&R>=r){
        make_tag(p,color);
        return; 
    }

    down(p);

    int mid=(l+r)>>1;
    if(L<=mid) modify(p<<1,l,mid,L,R,color);
    if(R>mid) modify(p<<1|1,mid+1,r,L,R,color);

    ans[p]=ans[p<<1]|ans[p<<1|1];
}

bitset<T> ask(int p,int l,int r,int L,int R){
    if(L<=l&&R>=r) return ans[p];

    down(p);

    bitset<T> res;
    int mid=(l+r)>>1;
    if(L<=mid) res|=ask(p<<1,l,mid,L,R);
    if(R>mid) res|=ask(p<<1|1,mid+1,r,L,R);

    return res;
}

int main(){

    scanf("%d%d%d",&n,&m,&q);
    modify(1,1,n,1,n,1);

    while(q--){
        char s[2];
        scanf("%s",s);
        if(*s=='C'){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            if(b<a) swap(a,b);
            scanf("%d%d%d",&a,&b,&c);
            modify(1,1,n,a,b,c);
        }
        else{
            int a,b;
            scanf("%d%d",&a,&b);
            if(b<a) swap(a,b);
            printf("%d\n",ask(1,1,n,a,b).count());
        }
    }

    return 0;
}

1.CF817F - MEX Queries

维护两个标记，
    1.区间覆盖(置0，置1)，覆盖时，翻转标记清除
    2.区间翻转，翻转时，如果有覆盖标记，直接翻转覆盖标记，否则，翻转标记取反
维护一个信息：区间和
线段树上二分，区间和小于区间长度，则有0。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10,M=N*3;

typedef long long ll;

int n;
struct node{
    int op;
    ll l,r;
}in[N];
vector<ll> alls;

struct node2{
    int la,lb;
    int cnt;
    node2():la(-1),lb(0),cnt(0){}
}tr[M<<2];

int find(ll x){
    return lower_bound(alls.begin(),alls.end(),x)-alls.begin();
}

void down(int p,int l,int r){
    if(tr[p].la!=-1){
        tr[p<<1].la=tr[p<<1|1].la=tr[p].la;
        tr[p<<1].lb=tr[p<<1|1].lb=0;

        int mid=(l+r)>>1;

        if(tr[p].la==1){
            tr[p<<1].cnt=mid-l+1;
            tr[p<<1|1].cnt=r-mid;
        }
        else tr[p<<1].cnt=tr[p<<1|1].cnt=0;
        tr[p].la=-1;
    }

    if(tr[p].lb){
        int mid=(l+r)>>1;

        if(tr[p<<1].la!=-1) tr[p<<1].la^=1;
        else tr[p<<1].lb^=1;
        tr[p<<1].cnt=mid-l+1-tr[p<<1].cnt;

        if(tr[p<<1|1].la!=-1) tr[p<<1|1].la^=1;
        else tr[p<<1|1].lb^=1;
        tr[p<<1|1].cnt=r-mid-tr[p<<1|1].cnt;
        tr[p].lb=0; 
    }

}

void modify(int p,int l,int r,int L,int R,int op){
    if(L<=l&&r<=R){
        if(op==1){
            tr[p].lb=0;
            tr[p].la=1;
            tr[p].cnt=r-l+1;
        }
        else if(op==2){
            tr[p].lb=0;
            tr[p].la=0;
            tr[p].cnt=0;
        }
        else{
            if(tr[p].la!=-1) tr[p].la^=1;
            else tr[p].lb^=1;
            tr[p].cnt=r-l+1-tr[p].cnt;
        }
        return;
    }

    down(p,l,r);
    int mid=(l+r)>>1;
    if(L<=mid) modify(p<<1,l,mid,L,R,op);
    if(R>=mid+1) modify(p<<1|1,mid+1,r,L,R,op);

    tr[p].cnt=tr[p<<1].cnt+tr[p<<1|1].cnt;
}

int ask(int p,int l,int r){
    if(l==r) {
        return l;   
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(tr[p<<1].cnt<mid-l+1) return ask(p<<1,l,mid);
    return ask(p<<1|1,mid+1,r);
}

int ask2(int p,int l,int r,int x){
    printf("%d %d %d\n",l,r,tr[p].cnt);
    if(l==r) {
        printf("%d, %d\n",alls[l],tr[p].cnt);
        return l;   
    }
    down(p,l,r);
    int mid=(l+r)>>1;
    if(x<=mid) ask2(p*2,l,mid,x);
    else ask2(p*2+1,mid+1,r,x);
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int op;
        ll l,r;
        scanf("%d%lld%lld",&op,&l,&r);
        in[i]={op,l,r};
        alls.push_back(l);
        alls.push_back(r);
        alls.push_back(r+1);
    }
    alls.push_back(1);

    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    for(int i=0;i<n;i++){
        auto &u=in[i];
        int l=find(u.l), r=find(u.r);
        modify(1,0,alls.size()-1,l,r,u.op);
        int p=ask(1,0,alls.size()-1);
        printf("%lld\n",alls[p]);
    }

    return 0; 
} 

先考虑暴力做法，再想怎么去优化

#include<bits/stdc++.h>

using namespace std;
const int N=5e3+10;

int n;
int a[N],cnt[N];
int ans[N];

int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    for(int i=1;i<=n;i++){
        memset(cnt,0,sizeof cnt);
        int id=i,mmax=-1;
        for(int j=i;j<=n;j++){
            int u=a[j];
            cnt[u]++;
            if(cnt[u]>mmax){
                id=u;
                mmax=cnt[u];
            }
            else if(cnt[u]==mmax&&u<id) id=u;
            ans[id]++;
        }
    }

    for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define mod 11380
const int N=12,M=32;

int L1,L2,L3,D;
int f[N][N][N][M];

int main(){

    scanf("%d%d%d%d",&L1,&L2,&L3,&D);

    for(int i=0;i<=D;i++) f[0][0][0][i]=1;
    for(int i=0;i<=L1;i++){
        for(int j=0;j<=L2;j++){
            for(int k=0;k<=L3;k++){
                for(int d=1;d<=D;d++){

                    for(int c=0;c<=k-1;c++){
                        int t=f[0][0][c][d-1]*f[i][j][k-c-1][d]%mod;
                        f[i][j][k][d]=(f[i][j][k][d]+t)%mod;
                    }

                    for(int b=0;b<=j-1;b++){
                        for(int c=0;c<=k;c++){
                            int t=f[0][b][c][d-1]*f[i][j-b-1][k-c][d]%mod;
                            f[i][j][k][d]=(f[i][j][k][d]+t)%mod;
                        }
                    }

                    for(int a=0;a<=i-1;a++){
                        for(int b=0;b<=j;b++){
                            for(int c=0;c<=k;c++){
                                int t=f[a][b][c][d-1]*f[i-a-1][j-b][k-c][d]%mod;
                                f[i][j][k][d]=(f[i][j][k][d]+t)%mod;
                            }
                        }    
                    }

                }
            }
        }
    }

    printf("%d\n",D?(f[L1][L2][L3][D]+-f[L1][L2][L3][D-1]+mod)%mod:f[L1][L2][L3][D]);

    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N=6e4+10;

int v[100],cnt;
bool f[N];

int main(){

    while(true){
        int sum=0;
        cnt=0;
        for(int i=1;i<=6;i++){
            int s;
            scanf("%d",&s);
            sum+=s*i;
            int k=1;
            while(k<=s){
                v[++cnt]=k*i;
                s-=k;
                k*=2;
            }
            if(s>0) v[++cnt]=s*i;
        }
        if(!sum) return 0;

        if(sum%2){
            puts("Can't");
            continue;
        }
        int m=sum/2;
        memset(f,0,sizeof f);
        f[0]=true;
        for(int i=1;i<=cnt;i++){
            for(int j=m;j>=v[i];j--){
                f[j]=f[j]|f[j-v[i]];
            }
        }
        if(f[m]) puts("Can");
        else puts("Can't");
    }

    return 0;
}

开一个分享用于记录自己写过的DP题单

线性DP：

1. AcWing 313. 花店橱窗 
    Time: 2023.05.23
    描述：n类花按顺序排成一排放在m个花盆里，给出每类花在不同花盆的美观度，求美观度和的最大值。
    f[i,j]：= 第i类花只考虑放在前j个花瓶时的美观度最大值;
    状态计算: f[i,j] = max{v[i,k] + f[i-1}[k-1]}, 
              要留出i-1个花瓶放前面的花，计算好k的范围，i<=k<=j;
2. AcWing 318. 划分大理石
    Time: 2023.05.25
    描述：6种大理石价值为1-6，给出每种大理石数量，问能否分成两堆使价值相等。
    乍一看是多重背包的计数dp，用f[i][j]表示只考虑选前i类大理石作为其中一堆的所有方案中，
    价值刚好为j的方案数。但是方案数过大，会爆答案，只要有一种就可以了,用bool来存储；
    不过物品个数和价值都很大，TLE了。用二进制拆分来优化，变成01背包。
    bool f[i][j] := 只考虑选前i类大理石作为其中一堆的所有方案中，是否存在价值刚好为j的方案；
    状态计算：f[i][j] = f[i-1][j] | f[i-1][j-vi];
              f[1-6][0] = true;
3. AcWing 317. 陨石的秘密
    Time:2023.05.26
    描述：给你i对{},j对[],k对(),深度d，构造一字符串，满足[]里不能有(),{}里不能有[]和()
          求字符串深度为d的方案数。 

    f[i][j][k][d] := 由i对{},j对[],k对()构成，深度<=d的字符串的方案数;
    ans = f[i][j][k][d] - f[i][j][k][d-1];
    以左边第一个括号的类型划分集合；S = (A)B, [A]B, {A}B，3种情况的方案数累加起来。
    以[A]B为例，此时A没有{}，f[i][j][k][d] += ΣbΣc f[0][b][c][d-1]*f[i][j-b-1][k-c][d];

#include<bits/stdc++.h>

using namespace std;
const int N=1e2+10;

int n,m;
int f[N][N],pos[N][N],v[N][N];

void dfs(int i,int j){
    int k=pos[i][j];
    if(i-1>0) dfs(i-1,k-1);
    if(i-1>0) putchar(' ');
    printf("%d",k);
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) scanf("%d",&v[i][j]);
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=INT_MIN;
            for(int k=i;k<=j;k++){
                int t=v[i][k]+f[i-1][k-1];
                if(t>f[i][j]){
                    f[i][j]=t;
                    pos[i][j]=k;
                }
            }
        }
    }

    printf("%d\n",f[n][m]);
    dfs(n,m);
    for(int i=0;i<n;i++)

    return 0;
}