欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【XSY2720】区间第k小 整体二分 可持久化线段树

程序员文章站 2024-03-04 12:21:53
...

题目描述

  给你你个序列,每次求区间第k小的数。

  本题中,如果一个数在询问区间中出现了超过w次,那么就把这个数视为n

  强制在线。

  n100000,ai<n,wn

题解

  考虑整体二分。

  先看看离线要怎么做。

  现在我们要计算每个数对每个区间的贡献。

  对于每个询问区间和每种数,让这个区间最右边w个数对这个询问的贡献为1,第w+1个数对这个询问的贡献为w

  这样每个数的贡献就是二维平面上的一个矩形。可以用扫描线+线段树解决。

  时间复杂度:O(nlogn)

  但问题是强制在线。

  可以把这棵线段树可持久化。

  时间复杂度不变。

  总时间复杂度:O(nlog2n)

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>
#include<utility>
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
namespace sgt
{
    struct node
    {
        int ls,rs,v;
    };
    node a[50000010];
    int cnt;
    int insert(int p1,int l,int r,int v,int L,int R)
    {
        int p=++cnt;
        a[p]=a[p1];
        if(l<=L&&r>=R)
        {
            a[p].v+=v;
            return p;
        }
        int mid=(L+R)>>1;
        if(l<=mid)
            a[p].ls=insert(a[p].ls,l,r,v,L,mid);
        if(r>mid)
            a[p].rs=insert(a[p].rs,l,r,v,mid+1,R);
        return p;
    }
    int query(int p,int x,int L,int R)
    {
        if(L==R)
            return a[p].v;
        int s=a[p].v;
        int mid=(L+R)>>1;
        if(x<=mid)
            s+=query(a[p].ls,x,L,mid);
        else
            s+=query(a[p].rs,x,mid+1,R);
        return s;
    }
}
struct change
{
    int x,y1,y2,k,w;
    change(){}
    change(int a,int c,int d,int e,int f)
    {
        x=a;
        y1=c;
        y2=d;
        k=e;
        w=f;
//      printf("%d %d %d %d %d\n",x,y1,y2,k,w);
    }
};
int cmp(change a,change b)
{
    return a.x>b.x;
}
change c[1000010],c2[1000010];
int cnt;
int n,w,q,type;
int a[100010];
set<int> st[100010];
int rtcnt=0;
int ls[3000010];
int rs[3000010];
int crt;
vector<pii> d[3000010];
int build(int l,int r,int vl,int vr)
{
    if(vl==vr)
        return 0;
    int rr=++rtcnt;
    d[rr].push_back(pii());
    int now=0;
    int i;
    int vm=(vl+vr)>>1;
    int num=0;
    int cnt1=0;
    for(i=l;i<=r;i++)
    {
        if(i!=l&&c[i].x!=c[i-1].x&&num)
        {
            d[rr].push_back(pii(c[i-1].x,now));
            num=0;
        }
        if(c[i].k<=vm)
        {
            now=sgt::insert(now,c[i].y1,c[i].y2,c[i].w,1,n);
            num++;
            cnt1++;
        }
    }
    if(num)
        d[rr].push_back(pii(c[r].x,now));
    int l1=l,r1=l+cnt1;
    for(i=l;i<=r;i++)
        if(c[i].k<=vm)
            c2[l1++]=c[i];
        else
            c2[r1++]=c[i];
    for(i=l;i<=r;i++)
        c[i]=c2[i];
    ls[rr]=build(l,l+cnt1-1,vl,vm);
    rs[rr]=build(l+cnt1,r,vm+1,vr);
    return rr;
}
int get(vector<pii> &s,int x)
{
    if(s.size()==1)
        return 0;
    if(x>s[1].first)
        return 0;
    int l=1,r=s.size()-1;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(x>s[mid].first)
            r=mid-1;
        else
            l=mid;
    }
    return l;
}
int query(int rr,int l,int r,int k,int vl,int vr)
{
    if(vl==vr)
        return vl;
    int p=get(d[rr],l);
    int rt=d[rr][p].second;
    int s=sgt::query(rt,r,1,n);
    int vm=(vl+vr)>>1;
    if(k<=s)
        return query(ls[rr],l,r,k,vl,vm);
    else
        return query(rs[rr],l,r,k-s,vm+1,vr);
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    scanf("%d%d%d%d",&n,&w,&q,&type);
    int x,i;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=n;i>=1;i--)
    {
        x=a[i];
        st[x].insert(i);
        int ed2=n;
        if(st[x].size()>=w+1)
        {
            int ed=n;
            if(st[x].size()>=w+2)
            {
                set<int>::iterator p=st[x].end();
                p--;
                ed=*p-1;
                st[x].erase(p);
            }
            set<int>::iterator p=st[x].end();
            p--;
            c[++cnt]=change(i,*p,ed,x,-w);
            ed2=*p-1;
        }
        c[++cnt]=change(i,i,ed2,x,1);
    }
    sort(c+1,c+cnt+1,cmp);
    int crt=build(1,cnt,0,n);
    int l,r,k;
    int last=0;
    for(i=1;i<=q;i++)
    {
        scanf("%d%d%d",&l,&r,&k);
        if(type)
        {
            l^=last;
            r^=last;
            k^=last;
        }
        last=query(crt,l,r,k,0,n);
        printf("%d\n",last);
    }
    return 0;
}