NOI 十连测 Round 5 T1

SOL：

这是一个很骚的构造。我们把一条无向边拆成2条有向边，并且定义一个点的点权为所有指向它的边的权之和。

那么我们发现，2*ans= A选的点权- B选的点权。

当一边的两点被分别选时，其对答案的贡献为0，而在右边的柿子的贡献也为0，当被一个人选时，右式将其记了两次。

那么我们发现ans=sort（降序），simga a（奇数）-simga a（偶数）。

讲道理，数组写treap好蛋疼啊。

#include<bits/stdc++.h>
#define N 1000007
using namespace std;
inline int rop() {
    static int x=23333;
    return x^=x<<13,x^=x>>17,x^=x<<5;
}
struct Node{
    int son[2],key,val,siz,sum;
    Node() {}
    inline void pod(int x) {
       key=x;siz=1;sum=x;val=rop();son[0]=son[1]=0;
    }
    inline void pud();
}T[N];
#define M 100007
int root,a[M],k,x,y,z,tot,n,q,op,u[M],v[M],w[M],lastans,o,p;
inline void Node::pud() {
        siz=T[son[0]].siz+T[son[1]].siz+1;
        sum=T[son[0]].sum+(key-T[son[1]].sum)*((T[son[0]].siz&1)?-1:1);
}
#define sight(x) ('0'<=x&&x<='9')
inline void read(int &x){
    static char c;
    for (c=getchar();!sight(c);c=getchar());
    for (x=0;sight(c);c=getchar())x=x*10+c-48;
}
void write(int x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
inline void writeln(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('\n'); }
inline void writel(int x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); }
void split(int now,int k,int &x,int &y){
      if (!now) {x=y=0;return;}
      int cmp=T[T[now].son[0]].siz+1;
      if (cmp>k) y=now,split(T[y].son[0],k,x,T[y].son[0]); 
      else   x=now,split(T[x].son[1],k-cmp,T[x].son[1],y);
      T[now].pud(); 
}
int merge(int x,int y){
    if (!x||!y) return x+y;
    T[x].pud(); T[y].pud();
    if (T[x].val<T[y].val) 
    { T[x].son[1]=merge(T[x].son[1],y); T[x].pud(); return x;}
    T[y].son[0]=merge(x,T[y].son[0]); T[y].pud(); return  y;
}
inline int Kth(int x){
    static int rt,anw;
    rt=root; anw=0;
    while (rt) 
        if (T[rt].key<=x) rt=T[rt].son[0];
        else anw+=T[T[rt].son[0]].siz+1,rt=T[rt].son[1];  
    return anw;
} 
inline void ins(int X){
    if (!X) return;
    k=Kth(X);
    split(root,k,x,y); T[++tot].pod(X);
    root=merge(merge(x,tot),y);
} 
inline void del(int X){
    if (!X) return;
    k=Kth(X);
    split(root,k,x,y); split(y,1,y,z);
    root=merge(x,z);
}
int org;
signed main () {
    freopen("round.in","r",stdin);
    freopen("round.out","w",stdout);
    read(n); read(q); read(o);
    for (int i=1;i<=q;i++) {
      read(op);
      if (op) {
         read(u[++org]); read(v[org]); read(w[org]);
         u[org]^=o*lastans; v[org]^=o*lastans;
         del(a[u[org]]); 
         ins(a[u[org]]=a[u[org]]+w[org]);
         del(a[v[org]]); 
         ins(a[v[org]]=a[v[org]]+w[org]);
      }    else {
         read(p); p^=o*lastans;
         del(a[u[p]]); ins(a[u[p]]=a[u[p]]-w[p]);
         del(a[v[p]]); ins(a[v[p]]=a[v[p]]-w[p]);
      }
      writeln(lastans=(T[root].sum>>1));
    } 
    return 0;
}

NOI 十连测 Round 5 T1

推荐阅读