题解 P3273 【[SCOI2011]棘手的操作】

· · 题解

看着道题的题解这么少，蒟蒻也来凑一篇。

蒟蒻调了两天的题目，不得不说是真的毒瘤。大佬们都用什么左偏树，可并堆啥的，弱弱的我只得用并查集+线段树。

在这里还要说一下，我用的是dfs序的线段树，据说要更优秀一点emmm，大家可以试着理解一下，只是标号方式不同，其他与普通的线段树没什么不同。此处不在赘述。模版链接线段树模版

思想： 现在我们只需要先模拟一遍加边过程（利用并查集），顺便把数据存储一下（面向数据的编程QAQ），然后重新把数据排个序，将同一个联通块内的数放在一起，再用线段树维护一下单点、区间修改和区间最大值查询。岂不美哉？

然鹅思想易懂，代码难写。并且为什么联通块内的点一定在一个连续的区间内呢？，这时候就要链表上场了QWQ。同摘录中说的，在并查集连边之后，一个联通块内的点都连成一条链，我们只要用双向链表把它们记下即可。可还记得邻接表，用相似的思想，我们写出了双向链表。

void unionn(int x,int y)
{
    int r1=find(x),r2=find(y);
    if(r1!=r2)
    {
        f[r2]=r1;
        int u=lst[r1],v=fir[r2];
        lst[r1]=lst[r2];
        pre[u]=v,next[v]=u;//双向链表!!!
    }
   // QAQ;
}

lst[]用来存主体（就像head[]数组），per[]和next[]一个正向，一个反向。同时我们发现，链表的加入与并查集的合并是一起的（废话，都写到一起了）,也就是说我们重建后的数组中同一联通块内的点一定在一个连续的区间内，而且顺序是加入的先后顺序，是不是很神奇？QWQ。

下面是重建数组部分

int tot = 0;
   for (int i = 1; i <= n; i++)//遍历一下找表头
        if (!pre[i])
            for (int j = i; j; j = next[j])//向后找儿子
                pos[j] = ++tot，newa[tot] = j;//newa->新数组（标记当前点在原数组中的位置）
                            //pos[]->反向记录位置。

再然后我们维护了一个l[]、一个r[]来记录左右边界（因为连续嘛）在重新建边是，只要如下就好，自己可以试着理解一下

code

void reunion(int x,int y)
{
    int r1=find(x),r2=find(y);
    if(r1!=r2)
    {
        f[r2]=r1;
        if(l[r1]<l[r2]) r[r1]=r[r2];
        else l[r1]=l[r2];
    }
}

emmmm，线段树部分和模板没什么差别，就讲这么多吧，毕竟还要靠自己去悟啊，多说无益，上代码！！

code

#include<iostream>
#include<cstdio>
#include<algorithm>
#define QAQ cout<<"debug"<<endl
const int  maxn = 3000000;
using namespace std;
int n,f[maxn],lst[maxn],next[maxn],pre[maxn],pos[maxn];
int l[maxn],r[maxn],cnt=1,newa[maxn],a[maxn],fir[maxn];
struct option
{
    int x,y,v;
    char opt;
}data[maxn];
struct segtree
{
    int lc,rc,sum,tag;
}tree[maxn];
//////////////////////
int find(int x)
{
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);
}
void unionn(int x,int y)
{
    int r1=find(x),r2=find(y);
    if(r1!=r2)
    {
        f[r2]=r1;
        int u=lst[r1],v=fir[r2];
        lst[r1]=lst[r2];
        pre[u]=v,next[v]=u;//双向链表!!!
    }
   // QAQ;
}
void reunion(int x,int y)
{
    int r1=find(x),r2=find(y);
    if(r1!=r2)
    {
        f[r2]=r1;
        if(l[r1]<l[r2]) r[r1]=r[r2];
        else l[r1]=l[r2];
    }
}
/////////并查集部分！！
/////////////////
void pushup(int u)
{
    tree[u].sum=max(tree[tree[u].lc].sum+tree[tree[u].lc].tag,tree[tree[u].rc].sum+tree[tree[u].rc].tag);
}//不多bb；
void pushdown(int u)
{
    tree[tree[u].lc].tag+=tree[u].tag;
    tree[tree[u].rc].tag+=tree[u].tag;
    tree[u].tag=0;
}//不多bb
void build(int u,int l,int r)//建树
{
    if(l==r)
    {
        tree[u].sum=a[newa[l]];
        return ;
    }
    tree[u].lc=++cnt;
    int mid=(l+r)>>1;
    build(tree[u].lc,l,mid);
    tree[u].rc=++cnt;
    build(tree[u].rc,mid+1,r);
    //tree[u].sum=max(tree[tree[u].lc].sum,tree[tree[u].rc].sum);
    pushup(u);
}
void add(int u,int l,int r,int ll,int rr,int w)
{
//  QAQ;
    if(l==ll&r==rr)
    {
        tree[u].tag+=w;
        return;
    }
    pushdown(u);
    int mid=(l+r)>>1;
    if(rr<=mid) add(tree[u].lc,l,mid,ll,rr,w);
    else if(ll>mid) add(tree[u].rc,mid+1,r,ll,rr,w);
    else
    {
        add(tree[u].lc,l,mid,ll,mid,w);
        add(tree[u].rc,mid+1,r,mid+1,rr,w);
    }
    pushup(u);
}
int query(int u,int l,int r,int ll,int rr)
{
    int ans=0;
    if(l==ll&r==rr)
        return tree[u].sum+tree[u].tag;
    pushdown(u);
    int mid=(l+r)>>1;
    if(rr<=mid) ans=query(tree[u].lc,l,mid,ll,rr);
    else if(ll>mid) ans=query(tree[u].rc,mid+1,r,ll,rr);
    else
    {
        ans=max(query(tree[u].lc,l,mid,ll,mid),query(tree[u].rc,mid+1,r,mid+1,rr));
    }
    pushup(u);
    return ans;
}
inline int read()
{
    int res = 0;
    bool bo = 0;
    char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-')
        ;
    if (c == '-')
        bo = 1;
    else
        res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
inline char get1()
{
    char c;
    while ((c = getchar()) != 'A' && c != 'F' && c != 'U')
        ;
    return c;
}
inline int get2()
{
    char c;
    while ((c = getchar()) < '0' || c > '9')
        ;
    return c - 48;
}
int main()
{
    int i, j, Q, id, tot = 0;
    n = read();
    for (i = 1; i <= n; i++)
        a[i] = read(),
        f[i] = fir[i] = lst[i] = i;
    Q = read();
    for (i = 1; i <= Q; i++)
    {
        char c = get1();
        switch (c)
        {
        case 'U':
            data[i].x = read();
            data[i].y = read();
            unionn(data[i].x, data[i].y);
            data[i].opt = 1;
            break;
        case 'A':
            id = get2();
            data[i].x = read();
            if (id < 3)
                data[i].y = read();
            data[i].opt = id + 1;
            break;
        case 'F':
            id = get2();
            if (id < 3)
                data[i].x = read();
            data[i].opt = id + 4;
            break;
        }
    }
    for (i = 1; i <= n; i++)
        if (!pre[i])
            for (j = i; j; j = next[j])
                newa[pos[j] = ++tot] = j;
    for (i = 1; i <= n; i++)
        f[i] = i, l[i] = r[i] = pos[i];
    build(1,1, n);
    for (i = 1; i <= Q; i++)
        switch (data[i].opt)
        {
        case 1:
            reunion(data[i].x, data[i].y);
            break;
        case 2:
            //cout<<data[i].y<<endl;
            add(1,1, n, pos[data[i].x], pos[data[i].x], data[i].y);
            break;
        case 3:
            id = find(data[i].x);
            add(1,1, n, l[id], r[id], data[i].y);
            break;
        case 4:
            add(1, 1,n, 1, n, data[i].x);
            break;
        case 5:
            printf("%d\n", query(1,1, n, pos[data[i].x], pos[data[i].x]));
            break;
        case 6:
            id = find(data[i].x);
            printf("%d\n", query(1,1, n, l[id], r[id]));
            break;
        case 7:
            printf("%d\n", query(1,1, n, 1, n));
            break;
        }
    return 0;
}

PS：主函数借鉴了一下n层楼上的代码，在此声明一下。

安利一下博客蒟蒻的blog