魔法少女LJJ

• 题目描述：

  在森林中见过会动的树，在沙漠中见过会动的仙人掌过后，魔法少女LJJ已经觉得自己见过世界上的所有稀奇古怪的事情了LJJ感叹道“这里真是个迷人的绿色世界,空气清新、淡雅,到处散发着醉人的奶浆味；小猴在枝头悠来荡去,好不自在；各式各样的鲜花争相开放,各种树枝的枝头挂满沉甸甸的野果；鸟儿的歌声婉转动听,小河里飘着落下的花瓣真是人间仙境”

  SHY觉得LJJ还是太naive，一天，SHY带着自己心爱的图找到LJJ，对LJJ说：“既然你已经见识过动态树，动态仙人掌了，那么今天就来见识一下动态图吧”

  LJJ：“要支持什么操作？”

  SHY：“

  1. 新建一个节点，权值为x。

  2. 连接两个节点。

  3.将一个节点a所属于的联通快内权值小于x的所有节点权值变成x。

  4.将一个节点a所属于的联通快内权值大于x的所有节点权值变成x。

  5.询问一个节点a所属于的联通块内的第k小的权值是多少。

  6.询问一个节点a所属联通快内所有节点权值之积与另一个节点b所属联通快内所有节点权值之积的大小。

  7.询问a所在联通快内节点的数量

  8.若两个节点a，b直接相连，将这条边断开。

  9.若节点a存在，将这个点删去。

  ” LJJ：“我可以离线吗？”

  SHY：“可以，每次操作是不加密的，”

  LJJ：“我可以暴力吗？”

  SHY：“自重”

  LJJ很郁闷，你能帮帮他吗?

• 输入格式:

  第一行有一个正整数m，表示操作个数。

  接下来m行，每行先给出1个正整数c。

  若c=1，之后一个正整数x，表示新建一个权值为x的节点，并且节点编号为n+1（当前有n个节点）。

  若c=2，之后两个正整数a，b，表示在a，b之间连接一条边。

  若c=3，之后两个正整数a，x，表示a联通快内原本权值小于x的节点全部变成x。

  若c=4，之后两个正整数a，x，表示a联通快内原本权值大于x的节点全部变成x。

  若c=5，之后两个正整数a，k，表示询问a所属于的联通块内的第k小的权值是多少。

  若c=6，之后两个正整数a，b，表示询问a所属联通快内所有节点权值之积与b所属联通快内所有节点权值之积的大小，

  若a所属联通快内所有节点权值之积大于b所属联通快内所有节点权值之积，输出1，否则为0。

  若c=7，之后一个正整数a，表示询问a所在联通块大小

• 这玩意是真毒瘤啊，数据结构都给我调傻了，耗了我一个下午啊

题目诈骗就不多说了，题意还是很好想的：联通块用并查集处理，修改我们可以考虑将对应的区间 \((1,a)\) 或 \((a,inf)\) 中的元素个数算出，统计为 \(t\) ,然后删除区间内的元素，再在 \(a\) 处重新加入 \(t\) 个元素 \(a\) ，使用动态开点插入元素；而对于维护乘积大小，我们考虑化积为和，利用 \(\log(nm)=\log(n)+\log(m)\)，将各个点权值取 \(\log\) 存入，这同样也能防止爆 \(long\) \(long\)

丑陋的代码

#include<bits/stdc++.h>
using namespace std;
#define M 1000000000
const int N=400010;
int n,cnt,tot;
int rt[N];
int fa[N];
struct TREE{
    bool tag;
    int dat,ls,rs;
    double logmul;
}t[N*19];
void push_down(int x){
    if(!t[x].tag) return;
    t[t[x].ls].dat=t[t[x].rs].dat=0,t[t[x].ls].logmul=t[t[x].rs]logmul=0;
    t[t[x].ls].tag=t[t[x].rs].tag=1,t[x].tag=0;
}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void insert(int &x,int p,int a,double v,int l,int r){
    if(!x) x=++tot;
    t[x].dat+=a,t[x].logmul+=a*v;
    if(l==r) return;
    push_down(x);
    int mid=(l+r)>>1;
    if(p<=mid) insert(t[x].ls,p,a,v,l,mid);
    else insert(t[x].rs,p,a,v,mid+1,r);
}
void del(int pos,int l,int r,int ll,int rr){
    if(!pos) return;
    if(l<=ll&&rr<=r){
        t[pos].dat=t[pos].logmul=0,t[pos].tag=1;
        return;
    }
    push_down(pos);
    int mid((ll+rr)>>1);
    if(l<=mid) del(t[pos].ls,l,r,ll,mid);
    if(mid<r) del(t[pos].rs,l,r,mid+1,rr);
    t[pos].dat=t[t[pos].ls].dat+t[t[pos].rs].dat;
    t[pos].logmul=t[t[pos].ls].logmul+t[t[pos].rs].logmul;
}
int query7(int pos,int l,int r,int b,int e){
    if(!pos) return 0;
    if(l<=b&&e<=r) return t[pos].dat;
    push_down(pos);
    int mid((b+e)>>1),ans(0);
    if(l<=mid) ans+=query7(t[pos].ls,l,r,b,mid);
    if(mid<r) ans+=query7(t[pos].rs,l,r,mid+1,e);
    return ans;
}
int query5(int x,int l,int r,int k){
    if(l==r) return l;
    push_down(x);
    int mid=(l+r)>>1;
    if(k<=t[t[x].ls].dat) return query5(t[x].ls,l,mid,k);
    else return query5(t[x].rs,mid+1,r,k -t[t[x].ls].dat);
}
int merge(int x , int y){
    if(!x||!y) return x+y;
    t[x].dat += t[y].dat,t[x].logmul+=t[y].logmul;
    push_down(x),push_down(y);
    t[x].ls=merge(t[x].ls,t[y].ls),t[x].rs=merge(t[x].rs ,t[y].rs);
    return x;
}
signed main(){
    int n,opt,a,x,k,t1,b;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&opt,&a);
        if(opt==1){
            insert(rt[++cnt],a,1,log(a),1,M);
            fa[cnt]=cnt;
        }
        if(opt==2){
            scanf("%d",&b);
            if(find(a)==find(b)) continue;
            rt[find(a)]=merge(rt[find(a)],rt[find(b)]);
            fa[find(b)]=fa[find(a)];
        }
        if(opt==3){
            scanf("%d",&x);
            t1=query7(rt[find(a)],1,x,1,M);
            del(rt[find(a)],1,x,1,M);insert(rt[find(a)],x,t1,log(x),1,M);
        }
        if(opt==4){
            scanf("%d",&x);
            t1=query7(rt[find(a)],x,M,1,M);
            del(rt[find(a)],x,M,1,M);insert(rt[find(a)],x,t1,log(x),1,M);
        }
        if(opt==5){
            scanf("%d",&k);
            printf("%d\n",query5(rt[find(a)],1,M,k));
        }
        if(opt==6){
            scanf("%d",&b);
            if(t[rt[find(a)]].logmul>t[rt[find(b)]].logmul) puts("1");
            else puts("0");
        }
        if(opt==7) printf("%d\n",t[rt[find(a)]].dat);
    }
    return 0;
}

离散化似乎是不需要的（仅代表个人观点）