题解：P16935 大图书管理员

· · 题解

信誓旦旦跑来开 H，第一遍推写了个很小清新的做法结果发现错掉了，后面发现要三个 BIT 来维护的时候……

我怀疑赤道大变了。

这个东西平方什么的看到的第一眼就想起了那个什么小 B 的询问，拉下去一看数据范围 10^5，这不就是给我们高贵的 O(n\sqrt n\log n) 莫队草的题么！果断考虑莫队。

首先 a_i\le 10^9 没啥用，容易发现超过 n 的都完全没用，于是直接把超过 n 的给压成 n 把值域给降下来。

每次加点的时候会多出一个位置的贡献，考虑直接对值域拍个维护指定范围内有多少数字的 BIT，然后直接算 T_i 直接计入贡献即可。

剩下的部分，考虑怎么快速维护 T_i 并统计贡献。

首先带权的一个平方显然是很难去区间修改的，考虑差分一下把区间修改给搞成单点修改，我们令 c_i=T_i-T_{i-1}，然后思考怎么去计算贡献。

我们假设 t 是当前元素影响到的范围。

到了喜闻乐见的推式子时间！

\begin{aligned} \sum_{i=1}^{t}i\times((T_i+1)^2-T_i^2) &=\sum_{i=1}^{t}i\times(2T_i+1) \\ &=\frac{t(t+1)}2+\sum_{i=1}^{t}2iT_i \\ &=\frac{t(t+1)}2+\sum_{i=1}^{t}2i\sum_{j=1}^ic_j \\ &=\frac{t(t+1)}2+\sum_{j=1}^tc_j\sum_{i=j}^{t}2i \\ &=\frac{t(t+1)}2+\sum_{j=1}^tc_j(t+j)(t-j+1) \\ &=\frac{t(t+1)}2+\sum_{j=1}^tc_j(t(t+1)-j(j-1)) \\ &=\frac{t(t+1)}2+t(t+1)\sum_{j=1}^tc_j-\sum_{j=1}^tc_jj(j-1) \\ \end{aligned}

于是再用两个 BIT 对差分数组维护 c_i 和 c_ii(i-1) 即可。

删除对称的反过来做即可。

时间复杂度 O(n\sqrt n\log n)，符合预期。

#include<bits/stdc++.h>
#define int long long
#define lowbit(x) x&(-x)
#define kuai 320
#define mod 1000000007
using namespace std;
int a[100005];
int n,m;
struct fish{
    int l,r,id;
}q[100005];
bool cmp(fish x,fish y){
    if(x.l/kuai==y.l/kuai){
        if((x.l/kuai)&1)return x.r<y.r;
        return x.r>y.r;
    }
    return x.l<y.l;
}
int ans[100005];
int siz,flc;
int tr[100005];
void add(int x,int v){
    for(int i=x;i<=n+2;i+=lowbit(i))
    tr[i]+=v;
}
int qry(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i))
    ans+=tr[i],ans%=mod;
    return ans;
}
int tr2[100005];
void add2(int x,int v){
    for(int i=x;i<=n+2;i+=lowbit(i))
    tr2[i]+=v;
}
int qry2(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i))
    ans+=tr2[i],ans%=mod;
    return ans;
}
int tr3[100005];
void add3(int x,int v){
    for(int i=x;i<=n+2;i+=lowbit(i))
    tr3[i]+=v;
}
int qry3(int x){
    int ans=0;
    for(int i=x;i;i-=lowbit(i))
    ans+=tr3[i],ans%=mod;
    return ans;
}
void ins(int x){
    int qwq=min(siz,x);
    add(x,1);
    siz++;
    flc=(flc+(siz-qry(siz-1))*(siz-qry(siz-1))%mod*siz%mod)%mod;
    flc=(flc+(qwq+1)*qwq%mod*(qry2(qwq))%mod)%mod;
    flc=(flc+(qwq+1)*qwq/2%mod)%mod;
    flc=(flc+qry3(qwq))%mod;
    add2(1,1);
    add2(x+1,-1);
    add3(x+1,x*(x+1));
}
void del(int x){
    int qwq=min(siz-1,x);
    flc=((flc-(siz-qry(siz-1))*(siz-qry(siz-1))%mod*siz%mod)%mod+mod)%mod;
    add(x,-1);
    siz--;
    add2(1,-1);
    add2(x+1,1);
    add3(x+1,-x*(x+1));
    flc=(flc-(qwq+1)*qwq%mod*(qry2(qwq))%mod)%mod;
    flc=(flc-(qwq+1)*qwq/2%mod)%mod;
    flc=(flc-qry3(qwq))%mod;
    flc+=mod;
    flc%=mod;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    cin>>a[i],a[i]=min(a[i],n);
    for(int i=1;i<=m;i++)
    cin>>q[i].l>>q[i].r,q[i].id=i;
    sort(q+1,q+1+m,cmp);
    int l=1,r=0;
    for(int i=1;i<=m;i++){
        while(l>q[i].l)l--,ins(a[l]);
        while(r<q[i].r)r++,ins(a[r]);
        while(l<q[i].l)del(a[l]),l++;
        while(r>q[i].r)del(a[r]),r--;
        ans[q[i].id]=flc;
    }
    for(int i=1;i<=m;i++)
    cout<<ans[i]<<'\n';
    return 0;
}
// 莫妮卡朝着远去的巴尼背影低头一鞠躬，以〈沉默魔女〉的身分开口：
//「……由衷感谢你，对本次任务所提供的协助。安柏德伯爵公子，巴尼琼斯大人。」

// 巴尼扭着脖子回头，向莫妮卡露出一记微笑。

// 那是从前莫妮卡泪眼汪汪地喊着「巴尼，救命啊」的时候，他总会摆出的「真拿你没办法」的笑容，令人怀念无比的笑容。

//「就是这样，你这种人，就尽管去一辈子感谢我吧。」