[BZOJ 3110] [ZJOI 2013] K 대수 조회 트 리 / CDQ 분할

트 리 세트 트 리 방법: 가중치 가 매우 작 다 는 것 을 알 게 되 었 습 니 다. 그래서 외층 의 가중치 선분 트 리 입 니 다. 내 부 는 동적 개방 점 의 구간 선분 트 리 입 니 다. 유지 권 치 는 [L, R] 에 있 고 위 치 는 [l, r] 에 있 는 수 는 모두 몇 개 입 니까?수정 은 내부 의 한 선분 나무 에 구간 을 하나 더 하 는 것 이다.조회 할 때 외층 선분 트 리 에서 왼쪽 나무 중 k 개수 가 충분 한 지 판단 하고, 충분 하면 왼쪽 나무 로 돌아 가 고, 부족 하면 줄 인 후 오른쪽 나무 로 돌아간다.코드 (MLE):

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
struct tree1
{
    int sum,lz;
    tree1 *ls,*rs;
    tree1()
    {
        sum=lz=0;
        ls=rs=NULL;
    }
    void cal(int x,int l,int r){sum+=x*(r-l+1);}
    void pushdown(int l,int r)
    {
        int mid=(l+r)>>1;
        if(ls==NULL) ls=new tree1;
        if(rs==NULL) rs=new tree1;
        ls->cal(lz,l,mid);rs->cal(lz,mid+1,r);
        ls->lz+=lz;rs->lz+=lz;
        lz=0;
    }
    void update()
    {
        sum=ls->sum+rs->sum;
    }
    void add(int lx,int rx,int l,int r)
    {
        if(lx==l&&rx==r) {lz++;sum+=r-l+1;return;}
        int mid=(l+r)>>1;
        pushdown(l,r);
        if(rx<=mid) ls->add(lx,rx,l,mid);
        else if(lx>mid) rs->add(lx,rx,mid+1,r);
        else ls->add(lx,mid,l,mid),rs->add(mid+1,rx,mid+1,r);
        update();
    }
    int qry(int lx,int rx,int l,int r)
    {
        if(lx==l&&rx==r) return sum;
        pushdown(l,r);
        int mid=(l+r)>>1;
        if(rx<=mid) return ls->qry(lx,rx,l,mid);
        else if(lx>mid) return rs->qry(lx,rx,mid+1,r);
        else return ls->qry(lx,mid,l,mid)+rs->qry(mid+1,rx,mid+1,r);
    }
};
struct tree2
{
    int l,r;
    tree2 *ls,*rs;
    tree1 *rt;
    tree2()
    {
        l=r=0;
        ls=rs=NULL;rt=NULL;
    }
    void build(int lx,int rx)
    {
        l=lx;r=rx;
        //(rt=new tree1)->init(1,n);
        rt=new tree1;
        //cout<
        if(l==r) return;
        int mid=(l+r)>>1;
        (ls=new tree2)->build(lx,mid);
        (rs=new tree2)->build(mid+1,rx);
    }
    void mdf(int lc,int rc,int c)
    {
        rt->add(lc,rc,1,n);
        if(l==r) return;
        int mid=(l+r)>>1;
        if(c<=mid) ls->mdf(lc,rc,c);
        else rs->mdf(lc,rc,c); 
    }
    int query(int lc,int rc,int k)
    {
        if(l==r) return l;
        int tmp=rs->rt->qry(lc,rc,1,n); 
        if(tmp<k) return ls->query(lc,rc,k-tmp);
        else return rs->query(lc,rc,k);
    }
}*xtr;
int main()
{
    scanf("%d%d",&n,&m);
    (xtr=new tree2)->build(0,n);
    while(m--)
    {
        int opt,a,b,c;
        scanf("%d%d%d%d",&opt,&a,&b,&c);
        if(opt==1) xtr->mdf(a,b,c);
        else printf("%d
",xtr->query(a,b,c));
    }
    return 0;
}

CDQ 분할 방법: solve (S, l, r) 는 조작 집합 이 S 라 고 표시 하고 그 중에서 모든 수정 작업 의 가중치 가 [l, r] 안에 있 으 며 질문 의 답 도 [l, r] 안에 있 으 며 모든 조작 은 시간 순서에 따른다.mid = (l + r) / 2, 우 리 는 먼저 [l, mid] 중의 수정 작업 을 할 수 있 습 니 다. 질문 답 이 [l, mid] 인지 [mid + 1, r] 인지 판단 한 다음 에 재 귀 하면 됩 니 다.나무 모양 배열 의 기이 한 기술 로 이 구간 과 구간 조 회 를 교묘 하 게 유지 하고 마지막 으로 빼 서 비 워 두 는 것 을 기억 하 세 요.코드 (AC):

#include
#include
#include
#include 
#define ll long long
using namespace std;
const int maxn=50010;
int n,m,ans[maxn];
ll c[2][maxn];
bool b[maxn];
struct node
{
    int o,x,y,z,id;
}q[maxn],nq[maxn];
bool cmp(node a,node b)
{
    return a.idint k,int x,int d)
{
    for(;x<=n;x+=(x&-x)) c[k][x]+=d;
}
ll qry(int k,int x)
{
    ll r=0;
    for(;x;x-=(x&-x)) r+=c[k][x];
    return r;
}
void mdf(int l,int r,int f)
{
    r++; 
    add(0,l,f);add(0,r,-f);add(1,l,f*l);add(1,r,-f*r);
}
ll qsum(int l,int r)
{
    l--;
    return qry(0,r)*(r+1)-qry(1,r)-qry(0,l)*(l+1)+qry(1,l);
}
void solve(int l,int r,int lx,int rx)
{
    if(lx>rx) return ;
    if(l==r)
    {
        for(int i=lx;i<=rx;i++)
            if(q[i].o) ans[q[i].id]=l;
        return ;    
    }
    int mid=(l+r)>>1;
    for(int i=lx;i<=rx;i++) b[i]=0;
    for(int i=lx;i<=rx;i++)
        if(q[i].o)
        {
            int tmp=qsum(q[i].x,q[i].y);
            if(tmp<q[i].z) {b[i]=1;q[i].z-=tmp;}
        }
        else if(q[i].z<=mid) mdf(q[i].x,q[i].y,1); else b[i]=1;
    for(int i=lx;i<=rx;i++)
        if(!q[i].o&&q[i].z<=mid) mdf(q[i].x,q[i].y,-1);
    int top=lx-1,smid;
    for(int i=lx;i<=rx;i++)
        if(!b[i]) nq[++top]=q[i];
    smid=top;   
    for(int i=lx;i<=rx;i++)
        if(b[i]) nq[++top]=q[i];
    for(int i=lx;i<=rx;i++) 
        q[i]=nq[i];
    solve(l,mid,lx,smid);
    solve(mid+1,r,smid+1,rx);               
}
int main()
{
    scanf("%d%d",&n,&m);
    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&q[i].o,&q[i].x,&q[i].y,&q[i].z);
        q[i].o--;q[i].id=i;
        if(q[i].o) q[i].id=++cnt;
        else q[i].z=n-q[i].z+1;
    }
    solve(1,n,1,m);
    for(int i=1;i<=cnt;i++)
        printf("%d
",n-ans[i]+1);
    return 0;
}