P10149 [Ynoi1999] XM66F

· · 题解

题解

Ynoi 的题就必须是紫黑是吧，这题蓝顶多了。这也是我第一篇 Ynoi 的题解。

先赌一把，看到数据范围为 n,m\le 5\times 10^5，时间限制为 3s，可以猜到是 O(n\sqrt{n}) 莫队。下面分类讨论 add 对答案的贡献，del 即为 add 的逆操作。

若 add 的数下标为 r+1，则对答案的贡献为：

\sum_{i=l}^{r}[a_{r+1}=a_i]\left(\sum_{j=1}^{r}[a_{r+1}>a_j]-\sum_{j=1}^{i-1}[a_i>a_j]\right)

若 add 的数下标为 l-1，则对答案的贡献为：

\sum_{i=l}^{r}[a_{l-1}=a_i]\left(\sum_{j=1}^{i-1}[a_{i}>a_j]-\sum_{j=1}^{l-2}[a_{l-1}>a_j]\right)

对于 u\in[1,n] 使用树状数组预处理 \displaystyle\sum_{i=1}^{u-1}[a_u>a_i] 即可。

其实到这里已经结束了，但是如果想让代码短一点的话，其实上面二个式子是可以合并的，这里不妨设 add 的数下标为 p\in\{l-1,r+1\}：

\sum_{i=l}^{r}[a_p=a_i]\left|~\sum_{j=1}^{i-1}[a_{i}>a_j]-\sum_{j=1}^{p-1}[a_p>a_j]~\right|

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
ll now,ans[maxn],sum[maxn];
int a[maxn],pre[maxn],cnt[maxn];
int n,m,len,tree[maxn];
inline void update(int p,int d){
    while(p<=n) tree[p]+=d,p+=(p&-p);
}
inline int query(int p){
    int res=0;
    while(p>=1) res+=tree[p],p-=(p&-p);
    return res;
}
inline void add(int i){
    now+=abs(1ll*pre[i]*cnt[a[i]]-sum[a[i]]);
    cnt[a[i]]++; sum[a[i]]+=pre[i];
    return; 
}
inline void del(int i){
    sum[a[i]]-=pre[i]; cnt[a[i]]--;
    now-=abs(1ll*pre[i]*cnt[a[i]]-sum[a[i]]);
    return;
}
struct node{int l,r,id;}qry[maxn];
inline bool comp(node u,node v){
    return u.l/len!=v.l/len?u.l<v.l:u.r<v.r;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;  
    len=sqrt(n);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) pre[i]=query(a[i]-1),update(a[i],1);
    for(int i=1;i<=m;i++) cin>>qry[i].l>>qry[i].r,qry[i].id=i;
    sort(qry+1,qry+1+m,comp);
    int l=1,r=0; 
    for(int i=1;i<=m;i++){
        while(l>qry[i].l) add(--l);
        while(r<qry[i].r) add(++r);
        while(l<qry[i].l) del(l++);
        while(r>qry[i].r) del(r--);
        ans[qry[i].id]=now;
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
    return 0;
}