zcmimi's blog
avatar
zc
2020-03-25 23:54:00
  • 本文总阅读量
查看原题

点击跳转

树套树

外层权值线段树 内层区间修改线段树

内层线段树需使用标记永久化,否则可能TLE

外层可以使用非递归结构提高速度

可以预先离散化提高速度

#include<bits/stdc++.h>
typedef long long ll;
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>inline void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>inline void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;inline void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}inline void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}inline void out(char c){pt(c);}template<typename T>inline void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>inline void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
const int N=50011;
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
int n,nn=0,q,sz=0,RT[N<<2],laz[N*400],ls[N*400],rs[N*400],C[N];
ll s[N*400];
struct que{int typ,l,r;ll c;}Q[N];
struct node{int v,id;bool operator<(node t){return v<t.v;}}b[N];
void upd(int L,int R,int l,int r,int &rt){
    if(!rt)rt=++sz;
    if(L<=l&&r<=R){s[rt]+=r-l+1;++laz[rt];return;}
    int m=(l+r)>>1;
    if(L<=m)upd(L,R,l,m,ls[rt]);
    if(R>m)upd(L,R,m+1,r,rs[rt]);
    s[rt]=s[ls[rt]]+s[rs[rt]]+(r-l+1)*laz[rt];
}
ll ask(int L,int R,int l,int r,int rt){
    if(!rt)return 0;
    if(L<=l&&r<=R)return s[rt];
    int m=(l+r)>>1;ll ans=laz[rt]*(min(R,r)-max(L,l)+1);
    if(L<=m)ans+=ask(L,R,l,m,ls[rt]);
    if(R>m)ans+=ask(L,R,m+1,r,rs[rt]);
    return ans;
}
#define ls rt<<1
#define rs rt<<1|1
void UPD(int L,int R,int v){
    int l=1,r=nn,rt=1;
    while(l<r){
        upd(L,R,1,n,RT[rt]);
        int m=(l+r)>>1;
        if(v<=m)r=m,rt=ls;
        else l=m+1,rt=rs;
    }
    upd(L,R,1,n,RT[rt]);
}
int ASK(int L,int R,ll k){
    int l=1,r=nn,rt=1;
    while(l<r){
        int m=(l+r)>>1;ll t=ask(L,R,1,n,RT[rs]);
        if(k>t)r=m,rt=ls,k-=t;
        else l=m+1,rt=rs;
    }
    return l;
}
int main(){
    in(n,q);
    int typ,l,r,d=0;ll c;
    for(int i=1;i<=q;++i){
        in(typ,l,r,c);
        if(typ==1)b[++nn]={c,i};
        Q[i]={typ,l,r,c};
    }
    std::sort(b+1,b+nn+1);b[0].v=-(1<<30);
    for(int i=1;i<=nn;++i)C[Q[b[i].id].c=d+=(b[i].v!=b[i-1].v)]=b[i].v;
    for(int i=1;i<=q;++i){
        l=Q[i].l,r=Q[i].r,c=Q[i].c;
        if(Q[i].typ==1)UPD(l,r,c);
        else out(C[ASK(l,r,c)],ln);
    }
    flush();
}

整体二分

比树套树常数小多了,简直吊着树套树打

#include<bits/stdc++.h>
#define il __inline__ __attribute__ ((always_inline))
typedef long long ll;
namespace IN{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}}using namespace IN;
namespace OUT{const char ln='\n';const int str=1<<20;static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(char c){pt(c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace OUT;
const int N=50001;
ll s[N],S[N];
int n,q,tot,ans[N];
il void upd(int x,int v){for(int i=x--;i<=n;i+=i&-i)s[i]+=v,S[i]+=v*x;}
#define upd(l,r,v) upd(l,v),upd(r+1,-v)
il ll ask(int x){ll res=0,RES=0;for(int i=x;i;i^=i&-i)res+=s[i],RES+=S[i];return x*res-RES;}
struct que{int typ,l,r,id;ll c;}a[N],a2[N];
void solve(int l,int r,int st,int ed){
    if(st>ed||l>r)return;
    if(l==r){for(int i=st;i<=ed;++i)ans[a[i].id]=l;return;}
    for(int i=st;i<=ed;++i)if(a[i].typ^1)goto ski;return;ski:;
    int m=(l+r)>>1,c1=0,c2=0;
    for(int i=st;i<=ed;++i)
    if(a[i].typ&1){
        if(a[i].c>m)upd(a[i].l,a[i].r,1),a2[++c2]=a[i];
        else a[st+c1++]=a[i];
    }
    else{
        ll x=ask(a[i].r)-ask(a[i].l-1);
        if(x>=a[i].c)a2[++c2]=a[i];
        else a[i].c-=x,a[st+c1++]=a[i];
    }
    for(int i=1;i<=c2;++i)if(a2[i].typ&1)upd(a2[i].l,a2[i].r,-1);
    for(int i=1;i<=c2;++i)a[st+c1+i-1]=a2[i];
    solve(l,m,st,st+c1-1);
    solve(m+1,r,st+c1,ed);
}
int main(){
    in(n,q);
    for(int i=1;i<=q;++i){
        in(a[i].typ,a[i].l,a[i].r,a[i].c);
        if(a[i].typ^1)a[i].id=++tot;
    }
    solve(1,n,1,q);
    for(int i=1;i<=tot;++i)out(ans[i],ln);
    flush();
}
LG 3332 [ZJOI2013]K大数查询
comment评论
Search
search