题解 P2345 【奶牛集会】

zhengzhi726 · 2019-03-09 11:40:20 · 题解

分块 发现还没有人用分块做这个题来着 提供新思路 n根n复杂度 这种千奇百怪的数据结构体 就是分块的很好的练手题 分块的具体细节大家自己也都会 上代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 20005
struct node{ll x,v;}s[maxn];
bool cmp(node a,node b){return a.v<b.v;}
ll n,m,k,a,b,c,ans=0,bs,mx,bn,pos[maxn],l[200],r[200],pre[200],nxt[200],sz[200],tag[maxn];
int main(){cin>>n;
    for(int i=1;i<=n;i++)cin>>s[i].v>>s[i].x,mx=max(s[i].x,mx);
    bs=sqrt(mx),bn=mx/bs;l[1]=1;
    ll now=0;for(int i=1;i<=bn;i++)r[i]=now+bs,now+=bs,l[i]=r[i-1]+1;r[bn]=mx;
    for(int i=1;i<=bn;i++)for(int j=l[i];j<=r[i];j++)pos[j]=i;sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++){ll p=pos[s[i].x];
        for(int j=1;j<p;j++)ans+=s[i].v*(sz[j]*(s[i].x-l[j])-pre[j]);
        for(int j=p+1;j<=bn;j++)ans+=s[i].v*(sz[j]*(r[j]-s[i].x)-nxt[j]);
        for(int j=l[p];j<=r[p];j++){
            if(tag[j])ans+=s[i].v*abs(j-s[i].x);
        }sz[p]++,pre[p]+=s[i].x-l[p],nxt[p]+=r[p]-s[i].x,tag[s[i].x]=1;
    }cout<<ans<<endl;return 0;
}