agc37f 思维/贪心

ruogu · 2019-10-22 08:12:44 · 个人记录

https://atcoder.jp/contests/agc037/tasks/agc037_f

一点也想不出。

具体看题解。

https://img.atcoder.jp/agc037/editorial.pdf

#include<bits/stdc++.h>
#define ld double
#define ull unsigned long long
#define ll long long
#define pii pair<int,int >
#define iiii pair<pii,pii >
#define mp make_pair
#define INF 1000000000
#define MOD 1000000007
#define rep(i,x) for(int (i)=0;(i)<(x);(i)++)
inline int getint(){
    int x=0,p=1;char c=getchar();
    while (c<=32)c=getchar();
    if(c==45)p=-p,c=getchar();
    while (c>32)x=x*10+c-48,c=getchar();
    return x*p;
}
using namespace std;
//ruogu_alter
const int N=2e5+5;
int n,l;
ll res;
pii b[N];
vector<iiii >a;
//
inline ll calc(vector<pii >&v){
    ll ans=0,sum=0;
    for(int i=l-1,j=0;i<v.size();i++,j++){
        sum+=1ll*v[j].first;
        ans+=1ll*v[i].second*sum;
    }
    return ans;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=getint();l=getint();
    rep(i,n){
        int x=getint();
        b[i]=mp(x,i);
    }
    sort(b,b+n);
    int pos=0,val=0;res=1ll*n;
    while(1){
        if(a.empty()){
            if(pos==n)break;
            else val=b[pos].first;
        }
        else ++val;
        while(pos<n&&b[pos].first==val){
            a.emplace_back(pii(b[pos].second,b[pos].second),pii(1,1));
            ++pos;
        }
        sort(a.begin(),a.end());
        vector<iiii >toa;
        for(int i=0,j;i<a.size();i=j+1){
            j=i;while(j<a.size()-1&&a[j].first.second+1==a[j+1].first.first)++j;
            int len=j-i+1,cnt=len/l;
            if(cnt){
                vector<pii >v,posx,posy;
                for(int k=i;k<=j;k++)v.push_back(a[k].second);
                res+=calc(v);
                rep(k,cnt){
                    posx.emplace_back(a[i].first.first+k,a[i].first.first+k);
                    posy.emplace_back(0,0);
                    if(k==cnt-1)posx.back().second=a[j].first.second;
                }
                for(int k=i;k<=j;k++){
                    int tx=k-i+1,ty=j-k+1;
                    if(tx>=l)posy[tx/l-1].second+=a[k].second.second;
                    if(ty>=l)posy[cnt-ty/l].first+=a[k].second.first;
                }
                res-=calc(posy);
                rep(k,posx.size())toa.emplace_back(posx[k],posy[k]);
            }
        }
        a=toa;
    }
    printf("%lld\n",res);
    return 0;
}