整体二分

ooliver的头像 发布于 14 小时前 9 次阅读 OI

P3834 【模板】可持久化线段树 2

模板，直接看代码：

#include<bits/stdc++.h>
using namespace std;

#define lowbit(x) x&-x
const int N=2e5+5;

int n,m,cnt;
int ans[N],tree[N];
int maxn=INT_MIN,minn=INT_MAX;

struct node{
    int x,y,k,id,op;
}q[N<<1],q1[N<<1],q2[N<<1];

struct BIT{
    int p[N];
    void add(int x,int k){
        for(int i=x;i<=n;i+=lowbit(i)) p[i]+=k;
    }
    int sum(int x){
        int res=0;
        for(int i=x;i>=1;i-=lowbit(i)) res+=p[i];
        return res;
    }
}bit;

void solve(int l,int r,int vl,int vr){
    if(l>r) return;
    if(vl==vr){
        for(int i=l;i<=r;i++)
            if(q[i].op) ans[q[i].id]=vl;
        return;
    }
    int mid=vl+vr>>1;
    int cnt1=0,cnt2=0;
    for(int i=l;i<=r;i++){
        if(!q[i].op){
            if(q[i].x<=mid){
                bit.add(q[i].id,1);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
        else{
            int s=bit.sum(q[i].y)-bit.sum(q[i].x-1);
            if(s>=q[i].k) q1[++cnt1]=q[i];
            else{
                q[i].k-=s;
                q2[++cnt2]=q[i];
            }
        }
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].op) bit.add(q1[i].id,-1);
    for(int i=1;i<=cnt1;i++) q[i+l-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[i+l+cnt1-1]=q2[i];
    solve(l,l+cnt1-1,vl,mid);
    solve(l+cnt1,r,mid+1,vr);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        q[++cnt]={x,0,0,i,0};
        minn=min(minn,x),maxn=max(maxn,x);
    }
    for(int i=1;i<=m;i++){
        int x,y,k;
        cin>>x>>y>>k;
        q[++cnt]={x,y,k,i,1};
    }
    solve(1,cnt,minn,maxn);
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}

P1527 [国家集训队] 矩阵乘法

上一题的二维版本，把树状数组改成二维的即可，代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lowbit(x) x&-x
const int N=505,M=5e5+5;

int n,m,cnt;
int ans[M];
int maxn=LONG_LONG_MIN,minn=LONG_LONG_MAX;

struct node{
    int x1,y1,x2,y2,k,id,op;
}q[M],q1[M],q2[M];

struct BIT{
    int p[N][N];
    void add(int x,int y,int k){
        for(int i=x;i<=n;i+=lowbit(i)) for(int j=y;j<=n;j+=lowbit(j)) p[i][j]+=k;
    }
    int sum(int x,int y){
        int res=0;
        for(int i=x;i>=1;i-=lowbit(i)) for(int j=y;j>=1;j-=lowbit(j)) res+=p[i][j];
        return res;
    }
}bit;

void solve(int l,int r,int vl,int vr){
    if(l>r) return;
    if(vl==vr){
        for(int i=l;i<=r;i++)
            if(q[i].op) ans[q[i].id]=vl;
        return;
    }
    int mid=vl+vr>>1;
    int cnt1=0,cnt2=0;
    for(int i=l;i<=r;i++){
        if(!q[i].op){
            if(q[i].id<=mid){
                bit.add(q[i].x1,q[i].y1,1);
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
        else{
            int s=bit.sum(q[i].x2,q[i].y2)-bit.sum(q[i].x1-1,q[i].y2)-bit.sum(q[i].x2,q[i].y1-1)+bit.sum(q[i].x1-1,q[i].y1-1);
            if(s>=q[i].k) q1[++cnt1]=q[i];
            else{
                q[i].k-=s;
                q2[++cnt2]=q[i];
            }
        }
    }
    for(int i=1;i<=cnt1;i++) if(!q1[i].op) bit.add(q1[i].x1,q1[i].y1,-1);
    for(int i=1;i<=cnt1;i++) q[i+l-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[i+l+cnt1-1]=q2[i];
    solve(l,l+cnt1-1,vl,mid);
    solve(l+cnt1,r,mid+1,vr);
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
        int x;
        cin>>x;
        q[++cnt]={i,j,0,0,0,x,0};
        minn=min(minn,x),maxn=max(maxn,x);
    }
    for(int i=1;i<=m;i++){
        int x1,y1,x2,y2,k;
        cin>>x1>>y1>>x2>>y2>>k;
        q[++cnt]={x1,y1,x2,y2,k,i,1};
    }
    solve(1,cnt,minn,maxn);
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}

P3527 [POI 2011] MET-Meteors

每次询问的答案具有单调性，考虑整体二分。

相对于模板，把树状数组的操作改为区间修改、单点查询，注意在计算时要把每个国家所占所有轨道都计算上。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int unsigned long long
#define lowbit(x) x&-x
const int N=3e5+5;

int n,m,k;
int o[N<<1],ans[N];
vector<int> g[N<<1];

struct node{
    int x,y,a,id;
}rain[N];

struct ask{
    int p,id;
}q[N<<1],q1[N<<1],q2[N<<1];

struct BIT{
    int tr[N<<1];
    void add(int x,int k){
        for(int i=x;i<=m*2;i+=lowbit(i)) tr[i]+=k;
    }
    int sum(int x){
        int res=0;
        for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];
        return res;
    }
}bit;

int check(int col){
    int res=0;
    for(int v:g[col]) res+=bit.sum(v);
    return res;
}

void solve(int l,int r,int l1,int r1){
    if(l1>r1) return;
    if(l==r){
        for(int i=l1;i<=r1;i++) ans[q[i].id]=l;
        return;
    }
    int mid=l+r>>1;
    for(int i=l;i<=mid;i++) bit.add(rain[i].x,rain[i].a),bit.add(rain[i].y+1,-rain[i].a);
    int cnt1=0,cnt2=0;
    for(int i=l1;i<=r1;i++){
        int k=check(q[i].id);
        if(k>=q[i].p) q1[++cnt1]=q[i];
        else{
            q[i].p-=k;
            q2[++cnt2]=q[i];
        }
    }
    for(int i=l;i<=mid;i++) bit.add(rain[i].x,-rain[i].a),bit.add(rain[i].y+1,rain[i].a);
    for(int i=1;i<=cnt1;i++) q[i+l1-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[i+l1+cnt1-1]=q2[i];
    solve(l,mid,l1,l1+cnt1-1);
    solve(mid+1,r,l1+cnt1,r1);
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>o[i];
        o[i+m]=o[i];
        g[o[i]].push_back(i),g[o[i]].push_back(i+m);
    }
    for(int i=1;i<=n;i++) cin>>q[i].p,q[i].id=i;
    cin>>k;
    for(int i=1;i<=k;i++){
        int x,y,a;
        cin>>x>>y>>a;
        if(x>y) y+=m;
        rain[i]={x,y,a,i};
    }
    solve(1,k+1,1,n);
    for(int i=1;i<=n;i++){
        if(ans[i]>k) cout<<"NIE\n";
        else cout<<ans[i]<<"\n";
    }
    return 0;
}

P3332 [ZJOI2013] K 大数查询

相较于板子发现需要一个支持区间修改和区间查询的数据结构，考虑线段树，其它都差不多了。

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lc p<<1
#define rc p<<1|1
#define lowbit(x) x&-x
const int N=3e5+5;

int n,m,cnt;
int o[N<<1],ans[N];

struct node{
    int x,y,k,id,op;
}q[N],q1[N<<1],q2[N<<1];

struct SEG{
    struct TREE{
        int l,r,sum,lazy;
        void tag(int k){
            sum+=k*(r-l+1);
            lazy+=k;
        }
    }tr[N<<2];
    void pushup(int p){
        tr[p].sum=tr[lc].sum+tr[rc].sum;
    }
    void pushdown(int p){
        if(tr[p].lazy){
            tr[lc].tag(tr[p].lazy);
            tr[rc].tag(tr[p].lazy);
            tr[p].lazy=0;
        }
    }
    void build(int p,int l,int r){
        tr[p].l=l,tr[p].r=r;
        if(l==r){
            tr[p].sum=0;
            return;
        }
        int mid=l+r>>1;
        build(lc,l,mid);
        build(rc,mid+1,r);
        pushup(p);
    }
    void change(int p,int l,int r,int k){
        if(tr[p].l>=l&&tr[p].r<=r){
            tr[p].tag(k);
            return;
        }
        pushdown(p);
        int mid=tr[p].l+tr[p].r>>1;
        if(l<=mid) change(lc,l,r,k);
        if(r>mid) change(rc,l,r,k);
        pushup(p);
    }
    int check(int p,int l,int r){
        if(tr[p].l>=l&&tr[p].r<=r) return tr[p].sum;
        pushdown(p);
        int mid=tr[p].l+tr[p].r>>1,ans=0;
        if(l<=mid) ans+=check(lc,l,r);
        if(r>mid) ans+=check(rc,l,r);
        return ans;
    }
}tree;

void solve(int l,int r,int l1,int r1){
    if(l1>r1) return;
    if(l==r){
        for(int i=l1;i<=r1;i++) if(q[i].op==2) ans[q[i].id]=l;
        return;
    }
    int mid=l+r>>1;
    int cnt1=0,cnt2=0;
    for(int i=l1;i<=r1;i++){
        if(q[i].op==1){
            if(q[i].k>mid){
                tree.change(1,q[i].x,q[i].y,1);
                q2[++cnt2]=q[i];
            }
            else q1[++cnt1]=q[i];
        }
        else{
            int vis=tree.check(1,q[i].x,q[i].y);
            if(q[i].k>vis){
                q[i].k-=vis;
                q1[++cnt1]=q[i];
            }
            else q2[++cnt2]=q[i];
        }
    }
    for(int i=l1;i<=r1;i++) if(q[i].op==1) if(q[i].k>mid) tree.change(1,q[i].x,q[i].y,-1);
    for(int i=1;i<=cnt1;i++) q[i+l1-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[i+l1+cnt1-1]=q2[i];
    solve(l,mid,l1,l1+cnt1-1);
    solve(mid+1,r,l1+cnt1,r1);
}

signed main(){
    cin>>n>>m;
    tree.build(1,1,n);
    for(int i=1;i<=m;i++){
        cin>>q[i].op>>q[i].x>>q[i].y>>q[i].k;
        if(q[i].op==2) q[i].id=++cnt;
    }
    solve(-n,n,1,m);
    for(int i=1;i<=cnt;i++) cout<<ans[i]<<"\n";
    return 0;
}

P7424 [THUPC 2017] 天天爱射击

答案明显具有单调性，考虑整体二分。

其余二分答案没啥好说的，一个答案区间，一个处理询问区间，先假设答案区间前一半的子弹都发射，再把询问区间的木板分成两部分，这些都是整体二分的套路。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define lowbit(x) x&-x
const int N=5e5+5;

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

struct node{
    int x,y,k,id;
}q[N],q1[N<<1],q2[N<<1];

struct BIT{
    int tr[N<<1];
    void add(int x,int k){
        for(int i=x;i<N;i+=lowbit(i)) tr[i]+=k;
    }
    int sum(int x){
        int res=0;
        for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];
        return res;
    }
}bit;

void solve(int l,int r,int l1,int r1){
    if(l1>r1) return;
    if(l==r){
        for(int i=l1;i<=r1;i++) if(q[i].k==1&&q[i].x<=a[l]&&q[i].y>=a[r]) ans[l]++;
        return;
    }
    int mid=l+r>>1;
    int cnt1=0,cnt2=0;
    for(int i=l;i<=mid;i++) bit.add(a[i],1);
    for(int i=l1;i<=r1;i++){
        int vis=bit.sum(q[i].y)-bit.sum(q[i].x-1);
        if(vis<q[i].k){
            q[i].k-=vis;
            q2[++cnt2]=q[i];
        }
        else q1[++cnt1]=q[i];
    }
    for(int i=l;i<=mid;i++) bit.add(a[i],-1);
    for(int i=1;i<=cnt1;i++) q[i+l1-1]=q1[i];
    for(int i=1;i<=cnt2;i++) q[i+l1+cnt1-1]=q2[i];
    solve(l,mid,l1,l1+cnt1-1);
    solve(mid+1,r,l1+cnt1,r1);
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>q[i].x>>q[i].y>>q[i].k;
    for(int i=1;i<=m;i++) cin>>a[i];
    solve(1,m,1,n);
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}