P11244 吻秋题解

MightZero · 2024-11-02 20:15:42 · 题解

被叉掉了/ll

Solution

~~我会暴力数据结构！~~

看到排序这一操作，不难想到可以用动态开点权值线段树维护序列，这样得到的序列就是天然有序的。

对每个序列建一棵权值线段树，操作一就等价于合并序列 a_x 与 a_y 所在的权值线段树，再将合并后的权值线段树按照排名 n 分裂得到新的 a_x 与 a_y。

对于操作二，若一个序列从未被排序过，直接输出原始值即可；否则只需要在 a_x 对应的权值线段树上查找排名为 y 的位置即可。

对于时间复杂度的分析： 设 V 为值域大小，modify，kth，split 的时间复杂度均为严格 O(\log V)，瓶颈主要在于 merge；merge 的时间复杂度主要取决于两棵线段树相交部分的大小，对两个实际值域不相交的序列对应的线段树做一次 merge 的时间复杂度约为 O(\log V)。而根据本题的结论，假设有 K 对序列的值域有交，那么若对两个实际值域有交的序列对应的线段树做一次 merge，最坏时间复杂度为 O(n\log V)，同时 K 至少会减少 1；由于 K 的上界为 \frac{m(m-1)}{2}，因此整体的最坏时间复杂度为 O((nm^2+q)\log V)，可能需要一定的卡常。

Code

这里为了卡常使用了非递归形式的 modify 与 kth；最慢的测试点约 1.7s，喜提本题最劣解/qd。

AC记录

#include<bits/stdc++.h>
#define loop(x,l,r) for(register int (x) = (l);(x)<=(r);++(x))
#define rloop(x,l,r) for(register int (x) = (r);(x)>=(l);--(x))
#define elif else if
using namespace std;
namespace FastIO {
    char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p1 = buf, p2 = (p1 + fread(buf, 1, 1 << 21, stdin))) == p1 ? EOF : *p1++)
    inline int read() { int x = 0, w = 0; char ch = getchar(); while (ch < '0' || ch > '9') w |= (ch == '-'), ch = getchar(); while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ '0'), ch = getchar(); return w ? -x : x; }
}; using namespace FastIO;
#undef getchar()
const int N=2e6+5,M=25;
#define ls tr[rt].Ls
#define rs tr[rt].Rs
int pcnt;
struct node{int Ls,Rs,val;}tr[N<<6];
inline void modify(int& rt,int L,int R,const int& p,const int& x)
{
    if(!rt)rt=++pcnt;
    register int nrt=rt;
    while(L<R)
    {
        tr[nrt].val+=x;
        register int mid=L+R>>1;
        if(p<=mid)
        {
            if(!tr[nrt].Ls)tr[nrt].Ls=++pcnt;
            nrt=tr[nrt].Ls;
            R=mid;
        }
        else
        {
            if(!tr[nrt].Rs)tr[nrt].Rs=++pcnt;
            nrt=tr[nrt].Rs;
            L=mid+1;
        }
    }
    tr[nrt].val+=x;
}
inline void split(int& rt,int L,int R,int& tar,int k)
{
    if(!rt)return;
    int lval=tr[ls].val;
    register int mid=L+R>>1;
    if(!tar)tar=++pcnt;
    if(k>lval)split(tr[rt].Rs,mid+1,R,tr[tar].Rs,k-lval);
    else 
    {
        swap(tr[rt].Rs,tr[tar].Rs);
        if(k<lval)split(tr[rt].Ls,1,mid,tr[tar].Ls,k);
    }
    tr[tar].val=tr[rt].val-k;
    tr[rt].val=k;
}
inline void merge(int& rtx,int& rty,int L,int R)
{
    if(!rtx||!rty)return rtx=rtx+rty,void();
    tr[rtx].val+=tr[rty].val;
    if(L==R)return;
    register int mid=L+R>>1;
    merge(tr[rtx].Ls,tr[rty].Ls,L,mid);
    merge(tr[rtx].Rs,tr[rty].Rs,mid+1,R);
}
inline int kth(int rt,int L,int R,int k)
{
    while(L<R)
    {
        register int mid=L+R>>1;
        if(k<=tr[ls].val)R=mid,rt=ls;
        else L=mid+1,k-=tr[ls].val,rt=rs;
    }
    return L;
}
#undef ls
#undef rs

int n,m,q,root[M],V;
bool md[M];
int a[M][N];
signed main()
{
    n=read(),m=read(),q=read();
    loop(i,1,m)
    {
        loop(j,1,n)
        {
            a[i][j]=read();
            V=max(a[i][j],V);
        }
    }
    loop(i,1,m)loop(j,1,n)modify(root[i],1,V,a[i][j],1);
    while(q--)
    {
        register int op=read(),x=read(),y=read();
        if(op==1)
        {
            md[x]=md[y]=1;
            merge(root[x],root[y],1,V);
            root[y]=0;
            split(root[x],1,V,root[y],n);
        }
        else
        {
            if(!md[x]) printf("%d\n",a[x][y]);
            else printf("%d\n",kth(root[x],1,V,y));
        }
    }
    return 0;
}

P11244 吻秋 题解

Solution

Code

P11244 吻秋题解