権値線分樹＋主席樹(区間K番目またはサブ区間のある原素の出現回数)

まず主席の木に行きます.区間Kの小さい板を求めます.

#include
#include
#include
#include
#define mid (l+r)/2
using namespace std;
const int N = 1e6+4;
int L[N<<5],R[N<<5],sum[N<<5];
int a[N],b[N],T[N];
int cnt,ss;
int build(int l,int r)
{
	int rt = ++cnt;
	sum[rt] = 0;
	if(l < r){
		L[rt] = build(l,mid);
		R[rt] = build(mid+1,r);
 	}
	return rt;
}
int update(int pre,int l,int r, int k){
	int rt = ++cnt;
	L[rt] = L[pre],R[rt] = R[pre],sum[rt] = sum[pre] +1; 
	if(l= r)return l;
	int x = sum[L[v]] - sum[L[u]];
	if(x >= k )return query(L[u] ,L[v] , l, mid ,k);
	else  return query(R[u] ,R[v] ,mid+1 ,r ,k-x);
} 
int main(){
	int n,m,q,p;
	scanf("%d%d",&n,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	m = unique(b+1,b+1+n)-b-1;
	T[0] = build(1,m);
//   
	for(int i = 1;i<=n;i++)
	{
		int t = lower_bound(b+1,b+1+m,a[i])-b;
		T[i] = update(T[i-1],1,m,t);
	}
	while(p--){
		int z,y,x;
		scanf("%d%d%d",&x,&y,&z); 
		int t = query( T[x-1],T[y],1,m,z);
		printf("%d
",b[t]);
	}
	return 0;

これは普通の主席の木です.もちろんこのような注釈もないので、とりあえず権値線分樹の例を話します.杭電多校2019第3回Find the answer題意:Q組の見本例.各サンプル例の1行目はn、m、次の行n個(a[i])を与えます.各要素に対して、削除前に最も少ない要素はm以下とする.権力の線分樹を作って、離散化した後、mにいくつ集めるか調べてください.コードは下記の通りです.

#include
#define LL long long
#define PLL pair
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=2e5+50;
int n,N;
LL m,a[maxn],b[maxn],sum[maxn<<2],num[maxn<<2];
void init(){
    sort(b+1,b+1+n);
     N = unique(b+1,b+1+n)-b-1;
     for(int i=1;i<=n;i++)
     {
         a[i] = lower_bound(b+1,b+1+N,a[i])-b;
     }
}//    
void updata(int rt,int l,int r,int p)
{
    if(l==r)
    {
        sum[rt]+=b[l];    //    p   
        num[rt]++;        //    p   
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid)
        updata(rt<<1,l,mid,p);
    else
        updata(rt<<1|1,mid+1,r,p);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    num[rt]=num[rt<<1]+num[rt<<1|1];
}
PLL query1(int rt,int l,int r,LL k) //             
{
    if(l==r)
    {
        if(k%b[l]==0)
            return PLL(l,k/b[l]);    //       
        else                         //                  
            return PLL(l,k/b[l]+1);
    }
    int mid=(l+r)>>1;
    if(sum[rt<<1|1]>=k)    //        k，     
        return query1(rt<<1|1,mid+1,r,k);
    else
        return query1(rt<<1,l,mid,k-sum[rt<<1|1]); //       ，  k         
                                                 //（            ）
}
LL query2(int rt,int l,int r,int ql,int qr)  //    
{
    if(ql<=l&&r<=qr)
        return num[rt];
    if(rqr)
        return 0;
    int mid=(l+r)>>1;
    return query2(rt<<1,l,mid,ql,qr)+query2(rt<<1|1,mid+1,r,ql,qr);
}
int main()
{
    int Q;
    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%d %lld",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i]);
            b[i]=a[i];
        }
        init();    //   
        memset(sum,0,sizeof(sum));
        memset(num,0,sizeof(num));        
        LL sum=0,ans[maxn];
        
        for(int i=1;i<=n;i++)
        {
            sum+=b[a[i]];
            if(sum>m)                 
            {
                PLL temp=query1(1,1,N,sum-m);
                ans[i]=temp.second;   //              
                if(temp.first+1<=m)
                    ans[i]+=query2(1,1,N,temp.first+1,m);  //            
            }
            else
                ans[i]=0;
            updata(1,1,N,a[i]);
        }
        
        for(int i=1;i<=n;i++)
            printf("%lld ",ans[i]);
        printf("
");
    }
    return 0;
}

明らかにこのような建樹は前の元素しか調べられません.あるサブ区間で調べられません.だから私達は彼を恒久化して、主席の木になりました.区間のK番目の大きさを調べられます.ある元素を調べて何回も現れました.(???)例題杭電多校2019第4回K-th Cloosest Distanceは意味があります.n個の数字を与えられました.q回の問い合わせは毎回l、r、p、kを与えます.区間lを聞いてみます.r内の数字とpの差の絶対値の中で、k番目に大きいのはいくらですか?主席樹＋2分がなくなりました.

#include 
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6;
struct node{
    int val ,l,r;
}tree[N*40]; //
int root[N],cnt;
int n,q,a[N];
int update(int pre,int L,int R,int k)
{
    int ctt = ++cnt;
    tree[ctt] = tree[pre];
    tree[ctt].val ++ ;
    if(L==R)return ctt;
    int mid = (R+L)/2;
    if(mid >= k) tree[ctt].l = update(tree[pre].l,L,mid,k);
    else tree[ctt].r = update(tree[pre].r,mid+1,R,k);
    return ctt; 
}
int query(int pl, int pr, int l, int r, int rt, int lt) {
    if(pl <= l && r <= pr) {
        return tree[rt].val - tree[lt].val;
    }
    int mid = (l + r) >> 1;
    int res = 0;
    if(pl <= mid) res += query(pl, pr, l, mid, tree[rt].l, tree[lt].l);
    if(pr > mid) res += query(pl, pr, mid + 1, r, tree[rt].r, tree[lt].r);
    return res;
} 
int main(){
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cnt = 0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            root[i] = update(root[i-1],1,M,a[i]);
        }
        int prex=0,l,r,p,k;
        while(q--)
        {
            scanf("%d%d%d%d",&l,&r,&p,&k);
            l^= prex,r^=prex,p^=prex,k^=prex;
                   int     pl = 0, pr = M;
                while(pl <= pr) 
                {
                         int mid = (pl + pr) >> 1;
                             if(query(max(1, p - mid), min(M, p + mid), 1, M, root[r], root[l - 1]) >= k) 
                        {
                                prex = mid;
                                pr = mid - 1;
                                
                            }
                         else pl = mid + 1;
                    }
                printf("%d
",prex);
        }
        
    }
    return 0;
}

ありがとうございます.