loj3259. 「ROIR 2020 Day 1」对常规的斗争

loj3259. 「ROIR 2020 Day 1」对常规的斗争

---

Sol

每一种数字单独处理。

假设该数字出现情况形如 .... x....x.....x....

把每一个....的长度取出来，假设为L

那么1的答案就要减去L，2的要减去L-1....

模拟下即可

long long 要开够！！！

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define maxn 200005
#define p(x) lower_bound(a+1,a+m+1,x)-a 
using namespace std;
int n,m,s[maxn],a[maxn],v[maxn];
vector<int>G[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&s[i]);a[i]=s[i];
    }
    sort(a+1,a+n+1);
    m=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;i++)G[p(s[i])].push_back(i);
    for(int i=1;i<=m;i++){
        int la=0;
        for(int j=0;j<G[i].size();j++){
            v[G[i][j]-la-1]++;la=G[i][j];
        }
        v[n-la]++;
    }
    long long ans,Sum=0,num=0;
    for(int i=1;i<n;i++)Sum+=1LL*v[i]*i,num+=v[i];
    for(int i=1;i<=n;i++){
        ans=1LL*(n-i+1)*m-Sum;
        Sum=Sum-num;num-=v[i];
        printf("%lld ",ans);
    }puts("");
    return 0;
}