BZOJ3065 带插入区间K小值

题目传送门

题目大意

带插入、修改的区间k小值在线查询。

题解

调了一下午,最后发现错误如下

正确的:

 if (t[rt[k]].sum*alpha>max(t[rt[lson[k]]].sum,t[rt[rson[k]]].sum))
    {
        if (tmp)
        {
            if (lson[k]==tmp) rebuild(lson[k]);
            else rebuild(rson[k]);
            tmp=0;
        } 
    } 
	else tmp=k;

我写的:

	if (t[rt[k]].sum*alpha>max(t[rt[lson[k]]].sum,t[rt[rson[k]]].sum))
	{
		if (tmp)
		{
			if (lson[k]==tmp) rebuild(lson[k]);
			else rebuild(rson[k]);
			tmp=0;
		}
		else tmp=k;
	}

就因为这个

可能还是我太菜了。。

先说一下这题怎么做:

Q1.如何查不带插入的区间第k大?
A:我们可以用普通线段树套值域线段树
Q2.改变一个数的值呢?
A:树状数组套主席树,当然,上面的也行
Q3.那么在数列中插入一个数呢?
很容易想到用平衡树套线段树,但是平衡树是旋转的,而线段树是静态的,一用rotate。。瞬间复杂度爆炸。。
这时候我们可以想到用非旋转的平衡树来维护:
treap非旋转版(本蒟蒻并不会。。),
 朝鲜树(时间复杂度O(sqrt(n)),显然爆炸,学了也没什么用)
替罪羊树(好东西啊!!!!!)
{%vfk大神花式过了此题,但是卡了块状链表:(虽然我不会}
那么对于每一种操作
插入:由于外层平衡树的存在,所以找到这个数字的位置,然后根到其路径上所有节点的权值线段树中插入
修改:和插入差不多,自行YY
查询:直接找到查询区间的若干棵子树,合并成一棵权值线段树,做一下二分。
         (学习hzwer学长暴力合并。。。)
剩下的就是将删去的节点加以利用(因为修改的话是先删除,再插入)
代码如下(丑,勿喷)
#include<bits/stdc++.h>
#define N 10000010
#define M 70010
using namespace std;
const double alpha=0.75;
int tmp,n,m,cnt,ROOT;
vector <int> root,point,Q;
int v[M],dfn[M],rt[M],lson[M],rson[M];
struct node
{
    int l,r,sum;
}t[N];
inline int read()
{
    int ans=0,f=1;
    char ch=getchar();
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans*f;
}
inline int newnode()
{
    if (!Q.size()) return ++cnt;
    else
    {
        int k=Q.back();Q.pop_back();
        return k;
    }
}
void erase(int &x)
{
    if (!x) return;
    Q.push_back(x);
    erase(t[x].l);erase(t[x].r);
    t[x].sum=0;x=0;
}
void insert(int &k,int l,int r,int val,int f)
{
    if (!k) k=newnode();
    if (l==r)
    {
        t[k].sum+=f;
        return;
    }
    int mid=(l+r)>>1;
    if (val<=mid) insert(t[k].l,l,mid,val,f);
    else insert(t[k].r,mid+1,r,val,f);
    t[k].sum=t[t[k].l].sum+t[t[k].r].sum;
    if (!t[k].sum) erase(k);
}
void build(int &k,int l,int r)
{
    if (l>r) return;
    if (l==r)
    {
        k=dfn[l];
        insert(rt[k],0,70000,v[k],1);
        return;
    }
    int mid=(l+r)>>1;
    k=dfn[mid];
    build(lson[k],l,mid-1);build(rson[k],mid+1,r);
    for (int i=l;i<=r;i++)
        insert(rt[k],0,70000,v[dfn[i]],1);
}
void dfs(int &x)
{
    if (!x) return;
    erase(rt[x]);
    dfs(lson[x]);
    point.push_back(x);
    dfs(rson[x]);
    x=0;
}
void rebuild(int &x)
{
    dfs(x);
    int s=point.size();
    for (int i=0;i<s;i++)
        dfn[i+1]=point[i];
    build(x,1,s);
    point.clear();
}
void query(int K,int l,int r)
{
    int L=t[rt[lson[K]]].sum,R=t[rt[K]].sum;
    if (l==1 && r==R)
    {
        root.push_back(rt[K]);
        return;
    }
    if (l<=L+1 && r>=L+1) point.push_back(v[K]);
    if (r<=L) query(lson[K],l,r);
    else if (l>L+1) query(rson[K],l-L-1,r-L-1);
    else
    {
        if (l<=L) query(lson[K],l,L);
        if (R>L+1) query(rson[K],1,r-L-1);
    }
}
int solve(int L,int R,int K)
{
    query(ROOT,L,R);K--;
    int l=0,r=70000,s1=root.size(),s2=point.size();
    while (l<r)
    {
        int mid=(l+r)>>1,sum=0;
        for (int i=0;i<s1;i++) sum+=t[t[root[i]].l].sum;
        for (int i=0;i<s2;i++) 
            if (point[i]>=l && point[i]<=mid) sum++;
        if (K<sum)
        {
            for (int i=0;i<s1;i++) root[i]=t[root[i]].l;
            r=mid;
        }
        else
        {
            for (int i=0;i<s1;i++) root[i]=t[root[i]].r;
            l=mid+1;K-=sum;
        }
    }
    root.clear();point.clear();
    return l;
}
int modify(int k,int x,int val)
{
    insert(rt[k],0,70000,val,1);
    int temp,L=t[rt[lson[k]]].sum;
    if (L+1==x)
    {
        temp=v[k];
        v[k]=val;
    }
    else if (L>=x)
    {
        temp=modify(lson[k],x,val);
    }
    else
    {
        temp=modify(rson[k],x-L-1,val);
    }
    insert(rt[k],0,70000,temp,-1);
    return temp;
}
void ins(int &k,int x,int val)
{
    if (!k)
    {
        k=++n;
        insert(rt[k],0,70000,val,1);
        v[k]=val;
        return;
    }
    insert(rt[k],0,70000,val,1);
    int L=t[rt[lson[k]]].sum;
    if (L>=x)
    {
        ins(lson[k],x,val);
    }
    else
    {
        ins(rson[k],x-L-1,val);
    }
    if (t[rt[k]].sum*alpha>max(t[rt[lson[k]]].sum,t[rt[rson[k]]].sum))
    {
        if (tmp)
        {
            if (lson[k]==tmp) rebuild(lson[k]);
            else rebuild(rson[k]);
            tmp=0;
        } 
    } 
	else tmp=k;
}
int main()
{
	ROOT=0;
    n=read();
    for (int i=1;i<=n;i++) v[i]=read();
    for (int i=1;i<=n;i++) dfn[i]=i;
    build(ROOT,1,n);
    m=read();
    char ch[10];
    int x,y,key,last=0;
    while (m--)
    {
        scanf("%s",ch);
        x=read();y=read();
        x^=last;y^=last;
        if (ch[0]=='Q')
        {
            key=read();
            key^=last;
            last=solve(x,y,key);
            printf("%d\n",last);
        }
        else if (ch[0]=='M')
        {
            modify(ROOT,x,y);
        }
        else
        {
            tmp=0;
            ins(ROOT,x-1,y);
            if (tmp)
            {
                rebuild(ROOT);
                tmp=0;
            }
        }
    }
    return 0;
}

 

3 thoughts on “BZOJ3065 带插入区间K小值”

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注