[Baltic2004]sequence

布满荆棘的人生 2021-11-17 02:42 199阅读 0赞

IOI2005国集队论文上的例\[神仙\]题……

具体论证看论文吧233

#include <bits/stdc++.h>
    using namespace std;
    int N,M;
    long long ans;
    int val[1000005],size[1000005],a[1000005],cnt,rt[1000005],l[1000005],r[1000005];
    int Tree[1000005][2],fa[1000005],dis[1000005];
    int merge(int x,int y){
        if (x==0||y==0)
          return x+y;
        if (val[x]<val[y])
          swap(x,y);
        Tree[x][0]=merge(y,Tree[x][0]);
        size[x]=size[Tree[x][0]]+size[Tree[x][1]]+1;
        fa[Tree[x][0]]=x;
        if (dis[Tree[x][1]]<dis[Tree[x][0]])
        swap(Tree[x][1],Tree[x][0]);
        dis[x]=dis[Tree[x][0]]+1;
        return x;
    }
    int main()
    {
        scanf("%d",&N);
        for (int i=1;i<=N;i++){scanf("%d",&a[i]);    a[i]-=i;}
        int cnt=0;
        for (int i=1;i<=N;i++){
            val[i]=a[i];
            size[i]=1;
            Tree[i][0]=Tree[i][1]=dis[i]=0;
            cnt++;
            rt[cnt]=i;
            l[cnt]=r[cnt]=i;
            while (cnt>1&&val[rt[cnt]]<val[rt[cnt-1]]){
                cnt--;
                rt[cnt]=merge(rt[cnt],rt[cnt+1]);
                r[cnt]=r[cnt+1];
                while (2*size[rt[cnt]]>r[cnt]-l[cnt]+2)
                rt[cnt]=merge(Tree[rt[cnt]][1],Tree[rt[cnt]][0]);
            }
        }
        for (int i=1;i<=cnt;i++){
            long long qwq=val[rt[i]];
            for (int j=l[i];j<=r[i];j++)
                ans+=1ll*abs(qwq-a[j]);
        }
        cout<<ans;
        return 0;
    }

转载于:https://www.cnblogs.com/si--nian/p/10949946.html

发表评论取消回复

表情：

评论列表（有 0 条评论，199人围观）

还没有评论，来说两句吧...

相关阅读

相关环状序列(Circular Sequence,ACM/ICPC Seoul 2004,UVa1584)题解

文章目录题目描述输入输出原题（PDF）题目分析案例分析解题标程

浅浅的花香味﹌/ 2022年12月28日 04:24/ 0 赞/ 242 阅读

相关 HDU 1452 Happy 2004 快乐2004

HDU 1452 Happy 2004 快乐2004 ：[http://acm.hdu.edu.cn/showproblem.php?pid=1452][http_acm.hd

「爱情、让人受尽委屈。」/ 2022年07月29日 10:58/ 0 赞/ 136 阅读

相关 sequence to sequence

[论文 Sequence to Sequence Learning with Neural Networks][Sequence to Seque

Myth丶恋晨/ 2022年07月15日 10:39/ 0 赞/ 322 阅读

相关 hdu 2004 成绩转换

成绩转换 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

小灰灰/ 2022年06月17日 13:17/ 0 赞/ 142 阅读

相关 HDU - 2004

成绩转换 HDU - 2004 -------------------- Problem 输入一个百分制的成绩t，将其转换成对应的等级，具体转换规则如下：

古城微笑少年丶/ 2022年06月14日 10:25/ 0 赞/ 161 阅读

相关 hdoj no.2004

include<stdio.h> int main() { int score; int input;

Myth丶恋晨/ 2022年06月05日 02:14/ 0 赞/ 156 阅读

相关 [Ceoi2004]Journey

题目描述给出N个点，及你的出发点K. 接下来N-1行描述有关边的开始点，结束点，边长.保证图中不会有环接下来给出数字J，代表你要走多少个点. 接下

浅浅的花香味﹌/ 2021年12月24日 16:21/ 0 赞/ 151 阅读

相关 [Baltic2004]sequence

IOI2005国集队论文上的例\[神仙\]题…… 具体论证看论文吧233 include <bits/stdc++.h> using namespace s

布满荆棘的人生/ 2021年11月17日 02:42/ 0 赞/ 199 阅读

相关 NOI2004 降雨量

[\\(Problem Link\\)][Problem Link] 自适应辛普森,卡了一页的精度。。。毒瘤。 / @Date : 2019-07-30 07:

红太狼/ 2021年11月10日 23:28/ 0 赞/ 144 阅读

相关 BZOJ 1379: [Baltic2001]Postman 水题

1379: \[Baltic2001\]Postman Description 邮递员每天给N个村子的人送信,每个村子可能在某个十字路口上,或一条路的中央.

绝地灬酷狼/ 2021年09月30日 12:58/ 0 赞/ 214 阅读