[noip2017模拟t1]

发表于 2017-11-06   |   分类于 未分类  |  访问: 70 次


【题目描述】
终于,迎来了第三次所罗门海战。
夕立孤身突入美军中心,面对排成一列的敌舰,夕立准备等概率随机选择一
段区间 [l, r] 内的敌舰进行攻击。
第 i 只美军舰船的攻击力是 ai 。由于夕立掌握了一种叫做 “亵渎” 的
攻击方法,所以她可以取得的战果是 mex{a[i]} (l ≤ i ≤ r)
mex 表示集合中第一个没有出现的自然数。 (mex{0, 1, 2, 3, 5} = 4)
现在,即将葬身铁底湾的夕立想要知道,她期望能取得多少战果。由于时间
紧迫,只要知道所有情况下她能取得的战果之和就可以了。
【输入格式】
第一行包含一个整数 n ,表示序列的长度。
第二行包含 n 个非负整数 a1, a2, a3 … an,描述序列。
全国信息学奥林匹克联赛(NOIP2017)复赛模拟 提高组
第 7 页 共 8 页
【输出格式】
只含一个整数,表示夕立所有情况下所能取得的战果之和。
【输入输出样例】
3

0 1 3
5
【数据范围】
测试点编号
1 - 2 n≤200
3 - 5 n≤3000
6 - 10 n≤200000
ai≤10^9

用线段树维护区间最大的mex和mex值的和
最开始线段树表示的是所有以1为左端点的情况的mex值
然后一个数一个数删除
删掉一个数a[i]以后
只需要找到下一次这个数出现的位置
把它之前的这些mex>a[i]情况全部改成a[i]就可以了
这样答案就是把每次修改后的tree[1].sum累加起来就行了

#include <cstdio>
#include <iostream>
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
using namespace std;
typedef long long ll;
const int _maxn=200005;
struct e{
    ll maxn,sum,bz;
    e(){bz=-1;}
}tree[_maxn<<2];
int n,a[_maxn],po[_maxn],Next[_maxn],last[_maxn];
bool vis[_maxn];
int getint(){
    char ch=getchar();
    while(ch<'0' || ch>'9')
        ch=getchar();
    int ans=0;
    while(ch>='0' && ch<='9'){
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
void pushup(int p){
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
    tree[p].maxn=max(tree[p<<1].maxn,tree[p<<1|1].maxn);
}
void pushdown(int p,int l,int r,int mid){
    if(tree[p].bz==-1)    return;
    tree[p<<1].sum=(ll)(mid-l+1)*tree[p].bz;
    tree[p<<1].bz=tree[p].bz;
    tree[p<<1].maxn=tree[p].bz;
    tree[p<<1|1].sum=(ll)(r-mid)*tree[p].bz;
    tree[p<<1|1].bz=tree[p].bz;
    tree[p<<1|1].maxn=tree[p].bz;
    tree[p].bz=-1;
}
void build(int p,int l,int r){
    if(l==r){
        tree[p].sum=tree[p].maxn=po[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(p);
}
int getl(int p,int l,int r,int x){
    if(l==r)    return l;
    int mid=(l+r)>>1;
    pushdown(p,l,r,mid);
    if(tree[p<<1].maxn>x)
        return getl(lson,x);
    else
        return getl(rson,x);
}
void modify(int p,int l,int r,int y1,int y2,int z){
    if(l>=y1 && r<=y2){
        tree[p].sum=(ll)(r-l+1)*(ll)z;
        tree[p].bz=z;
        tree[p].maxn=z;
        return;
    }
    int mid=(l+r)>>1;
    pushdown(p,l,r,mid);
    if(mid>=y1)    modify(lson,y1,y2,z);
    if(mid<y2)    modify(rson,y1,y2,z);
    pushup(p);
}
int main(){
    freopen("yuudachi.in","r",stdin);
    freopen("yuudachi.out","w",stdout);
    scanf("%d",&n);
    int now=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]>n)    a[i]=n+1;
        vis[a[i]]=true;
        while(vis[now])
            ++now;
        po[i]=now;
    }
    for(int i=n;i>=1;i--){
        if(last[a[i]])
            Next[i]=last[a[i]];
        else
            Next[i]=n+1;
        last[a[i]]=i;
    }
    build(1,1,n);
    ll ans=0;
    int y1,y2;
    for(int i=1;i<=n;i++){
        ans+=tree[1].sum;
        if(tree[1].maxn>a[i]){
            y1=getl(1,1,n,a[i]);
            y2=Next[i]-1;
            if(y1<=y2)
                modify(1,1,n,y1,y2,a[i]);
        }
        modify(1,1,n,i,i,0);
    }
    printf("%lld\n",ans);
    return 0;
}

仅有 1 条评论


  1. 微信资源网

    感谢博主分享

    微信资源网 May 9th, 2018 at 05:48 pm回复

发表新评论

© 2017 Powered by Typecho & Theme Quark