P11365 Ynoi2024 新本格魔法少女りすか
神奇的压位树状数组……
思路
序列区间查询操作，考虑分块。
处理好散块与整块之间的贡献即可。
- 散块对散块：每次询问的区间产生的散块用树状数组计算贡献，复杂度 \(O(\sum m_i \sqrt{n\log n})\)。
- 整块对散块（区间）：枚举整块，处理 \(ressum_i\) 表示小于等于 \(i\) 的数在块内有多少个，在处理前缀和 \(sum_i\) 表示前 \(i\) 个数对整块的贡献和。然后枚举查询的区间，前缀和作差直接计算区间 \([l,r]\) 对于该块的贡献，复杂度 \(O(n\sqrt{n\log n})\)。
tips：整块的贡献可能算重，可以考虑只计算比自己小的整块的贡献。
总复杂度 \(O(n\sqrt{n\log n})\)。
压位树状数组
由于这是一个排列，我们把 \(i\) 在二进制位中的后六位拆下来，设二进制后六位组成的数是 \(x\)，在 \(b[i>>6]\) 中把第 \(x\) 位标为 \(1\)。同时，在树状数组 \((i>>6)+1\) 的位置加一。
查询时，除了正常的在树状数组查询，还需要在 \(b[i>>6]\) 加上小于 \(x\) 的位标为一的个数。
这样操作后，单次 \(\log n\) 的查询，变味了 \(\log(n/64)=\log n -6\) 次。
CODE
#include<bits/stdc++.h>
using namespace std;
const int maxB=6e3+5,maxn=5e5+5;
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
int n,m,B,cnt,N,ctt;
int M[maxn],a[maxn],ressum[maxn],mdf[maxn];
ll ans[maxn],sum[maxn];
pii qry[maxn];
inline int read()
{
char c=getchar();int fx=1,sum=0;
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
if(c=='-') c=getchar(),fx=-1;
while('0'<=c&&c<='9') sum=(sum<<1)+(sum<<3)+c-'0',c=getchar();
return sum*fx;
}
struct fknode1{int l,r;}fk[maxB];
class treearray
{
private:
#define lowbit(x) (x&(-x))
public:
int ts[500005];
ull b[500005];
inline void updata(int i,int y){
mdf[++ctt]=i;
b[i>>6]|=1ull<<(i&63),i>>=6,i++;while(i<=N) ++ts[i],i+=lowbit(i);}
inline void clr(int i){b[i>>=6]=0,i++;while(i<=N&&ts[i]) ts[i]=0,i+=lowbit(i);}
inline int getsum(int i){int res=__builtin_popcountll(b[i>>6]&(((i&63)==63?0:(1ull<<((i&63)+1)))-1));i>>=6;while(i) res+=ts[i],i-=lowbit(i);return res;}
}Ts;
inline ll add(int l,int r){ll sum=0;for(int i=l;i<=r;i++) sum+=Ts.getsum(a[i]-1);return sum;}
inline void upd(int l,int r){for(int i=l;i<=r;i++) Ts.updata(a[i],1);}
inline void clr()
{
if(ctt<=1200) for(int i=1;i<=ctt;i++) Ts.clr(mdf[i]);
else for(int i=0;i<=N;i++) Ts.b[i]=0,Ts.ts[i]=0;
ctt=0;
}
int main()
{
n=read(),m=read();N=(n>>6)+1;
B=350;
for(int i=1;i<=(n-1)/B+1;i++){fk[i].l=fk[i-1].r+1,fk[i].r=min(fk[i].l+B-1,n);}
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++)
{
int t=read();M[i]=cnt+1;
for(int j=0,l,r;j<t;j++)
{
l=read(),r=read(),qry[++cnt]=make_pair(l,r);
int numl=(l-1)/B+1,numr=(r-1)/B+1;
if(numl==numr) {if(r<fk[numl].r||l>fk[numl].l) ans[i]+=add(l,r),upd(l,r);}
else
{
if(l>fk[numl].l) ans[i]+=add(l,fk[numl].r);
if(r<fk[numr].r) ans[i]+=add(fk[numr].l,r);
if(l>fk[numl].l) upd(l,fk[numl].r);
if(r<fk[numr].r) upd(fk[numr].l,r);
}
}
clr();
}
M[m+1]=cnt+1;
for(int i=1;i<=(n-1)/B+1;i++)
{
for(int j=fk[i].l;j<=fk[i].r;j++) ressum[a[j]]++;
for(int j=1;j<=n;j++) ressum[j]+=ressum[j-1];
int det=fk[i].r-fk[i].l+1;
for(int j=1;j<fk[i].l;j++) sum[j]=sum[j-1]+(det-ressum[a[j]]);
for(int j=fk[i].l;j<=fk[i].r;j++) sum[j]=sum[j-1];
for(int j=fk[i].r+1;j<=n;j++) sum[j]=sum[j-1]+ressum[a[j]-1];
for(int j=1;j<=n;j++) ressum[j]=0;
for(int j=1;j<=m;j++)
{
int flg=0;ll res=0;
for(int k=M[j];k<M[j+1];k++)
{
pii v=qry[k];
if(v.fi<=fk[i].l&&fk[i].r<=v.se) {flg=1;continue;}
if(v.se<=fk[i].l) res+=sum[v.se]-sum[v.fi-1];
else
{
int l=v.fi,r=v.se,numl=(l-1)/B+1,numr=(r-1)/B+1;
if(numl==numr) {if(r<fk[numl].r||l>fk[numl].l) res+=sum[r]-sum[l-1];}
else
{
if(l>fk[numl].l) res+=sum[fk[numl].r]-sum[l-1];
if(r<fk[numr].r) res+=sum[r]-sum[fk[numr].l-1];
}
}
}
ans[j]+=res*flg;
}
}
for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
}