WNJXYK
Thanks to the cruel world.
WNJXYKのBlog
Educational Codeforces Round 51: 1051G. Distinctification
Educational Codeforces Round 51: 1051G. Distinctification

题目描述

给定一个长度为n的数对序列P = , , , \cdots, ,有两种可用操作:
1. 如果存在a_i = a_j, i\neq j,那么我们可以花费b_i的代价,令a_i \rightarrow a_i+1
2. 如果存在a_i=a_j+1, i\neq j,那么我们可以花费-b_i的代价,令a_i\rightarrow a_i-1
现在通过如上两种操作,令这个序列的每个数字不相同,所需要最小代价为f(P)
如果P_i为序列P长度为i的前缀,那么问f(P_1), f(P_2), \cdots, f(P_n)分别是多少。

题解

首先可以发现操作与对应代价是可逆的。
如果将数对的a_i排序,我们把可以连续操作的数对看做一个区间,我们可以通过对a_i的某种顺序的操作加减操作,使得最终这些a_i不相等且b_i的顺序任意。
对应操作的代价等于两个序列的某种类似乘积和相减,比如原来的数对序列为, , \cdots, 经过操作之后我们令其变成了, , \cdots,
那么操作对应的代价为(\sum_{i=1}^m a_i\times b_i) – (\sum_{i=1}^m c_i\times b_{p_i})
很明显,我们最终状态应该让b_i从大到小排列,我们只需要将一个区间的数对的b_i排序即可。
我们可以使用权值线段树来实现这个操作,动态插入一个点,可能会引起两颗线段树的合并。

代码

#include <cstdio>
#include <queue>
#define LL long long 
using namespace std;

const int RANGE=4e5;
const int MAXN=2e5+50;
struct Node{ LL a, b; }node[MAXN];

int n; LL ans;

struct BTree{ 
    int lx, rx;
    LL sum, ans, siz;
}tree[MAXN*30];
int numt; queue<int> que;

inline void update(int x, int l, int r){
    if (l==r) return;
    int lx=tree[x].lx, rx=tree[x].rx;
    tree[x].siz=tree[lx].siz+tree[rx].siz;
    tree[x].sum=tree[lx].sum+tree[rx].sum;
    tree[x].ans=tree[lx].ans+tree[rx].ans+tree[rx].siz*tree[lx].sum;
}

inline int newNode(){
    int r=0; if (!que.empty()) r=que.front(), que.pop(); else r=++numt;
    tree[r].lx=tree[r].rx=0; tree[r].ans=tree[r].sum=tree[r].siz=0;
    return r;
}

inline void delNode(int x){ 
    que.push(x); 
}

void modify(int &x, int l, int r, int p, int v){
    if (!x) x=newNode();
    if (l==r){
        tree[x].siz++;
        tree[x].sum+=v;
        tree[x].ans+=tree[x].siz*v;
    }else{
        int m=(l+r)/2;
        if (p<=m)
            modify(tree[x].lx, l, m, p, v);
        else modify(tree[x].rx, m+1, r, p, v);
        update(x, l, r);
    }
}

int merge(int x, int y, int l, int r){
    if (!x || !y) return x+y;
    int nx=newNode();
    if (l==r){
        tree[nx].siz=tree[x].siz+tree[y].siz;
        tree[nx].sum=tree[x].sum+tree[y].sum;
        tree[nx].ans=tree[x].ans+tree[y].ans+tree[x].sum*tree[y].siz;
    }else{
        int m=(l+r)/2;
        tree[nx].lx=merge(tree[x].lx, tree[y].lx, l, m);
        tree[nx].rx=merge(tree[x].rx, tree[y].rx, m+1, r);
        update(nx, l, r);
    }
    delNode(x); delNode(y);
    return nx;
}

int pos[MAXN*2];
int getPos(int x){ return pos[x]=(pos[x]==x?x:getPos(pos[x])); }

struct Block{
    int left, right;
    int root, next;
}block[MAXN*2];
int getBlock(int p){ return block[p].next=(block[p].next==p?p:getBlock(block[p].next)); }
inline void mergeBlock(int x, int y){
    x=getBlock(x); y=getBlock(y);
    // printf("Merge [%d, %d] & [%d, %d]\n", block[x].left, block[x].right, block[y].left, block[y].right); 
    ans-=(block[x].left-1)*tree[block[x].root].sum+tree[block[x].root].ans;
    ans-=(block[y].left-1)*tree[block[y].root].sum+tree[block[y].root].ans;
    /*printf("- %lld(%lld) %lld(%lld)\n", (block[x].left-1)*tree[block[x].root].sum+tree[block[x].root].ans, 
                                        tree[block[x].root].sum, 
                                        (block[y].left-1)*tree[block[y].root].sum+tree[block[y].root].ans,
                                        tree[block[y].root].sum);*/
    block[y].left=block[x].left;
    // printf("=> [%d, %d]\n", block[y].left, block[y].right);
    block[y].root=merge(block[x].root, block[y].root, 1, RANGE);
    ans+=(block[y].left-1)*tree[block[y].root].sum+tree[block[y].root].ans;
    // printf("+ %lld(%lld)\n", (block[y].left-1)*tree[block[y].root].sum+tree[block[y].root].ans, tree[block[y].root].ans);
    block[x].next=y;
}


int main(){
    // freopen("in.txt", "r", stdin);
    scanf("%d", &n);
    for (int i=1; i<=RANGE; i++) block[i].left=block[i].right=i, block[i].root=0, block[i].next=i, pos[i]=i;

    ans=0;
    for (int i=1, a, b; i<=n; i++){
        scanf("%d%d", &a, &b);
        int p=getPos(a); modify(block[p].root, 1, RANGE, b, b); pos[p]=p+1;
        ans-=1LL*a*b-1LL*p*b;
        if (block[p-1].root) mergeBlock(p-1, p);
        if (block[p+1].root) mergeBlock(p, p+1);
        printf("%lld\n", ans);
    }

    return 0;
}
赞赏
https://secure.gravatar.com/avatar/f83b57c055136369e9feba5d6671d6b5?s=256&r=g

WNJXYK

文章作者

一个蒟蒻

推荐文章

发表评论

textsms
account_circle
email

WNJXYKのBlog

Educational Codeforces Round 51: 1051G. Distinctification
题目描述 给定一个长度为$n$的数对序列$P = <a_1, b_1>, <a_2, b_2>, <a_3, b_3>, \cdots, <a_n, b_n>$,有两种可用操作: 1. 如果存在$a_i = a_j, i\neq j$,那么我们可以…
扫描二维码继续阅读
2018-09-30
<--! http2https -->