为什么会有文化课寒假作业？？？
P5046 [Ynoi2019 模拟赛] Yuno loves sqrt technology I
傻逼卡常题去似吧
强制在线考虑分块。先把区间的贡献给拆开，珂以拆成下面图的形式：
其中绿色是整块内部的贡献，橙色是单个散块内部贡献，蓝色是散块对散块的贡献，红色是散块和整块之间的贡献。考虑分开来处理四个部分。
橙色部分，单个块的贡献考虑用树状数组求出逆序对，没啥好说，注意我们后面要维护前后缀和的时候注意树状数组加减值是什么以及加减的顺序。
绿色珂以预处理一个 \(sum\) 表示 \(i\) 到 \(j\) 块的贡献，处理这个珂以先记录每个块中小于等于 \(x\) 的数的个数，然后对这个做块之间的前缀和，处理的时候假设左块为 \(i\) 右块为 \(j\)，对于 \(j\) 块的每一个数差分出前面比它大的数的个数，求和，最后加上 \(j\) 块内部的贡献还有 \(sum[i][j-\mathbf{1}]\)。
蓝色可以考虑新开一个数组赋值原数组，然后对这个数组在每个块内从小到大排序，还要按他原来的位置排。查询的时候就两个单调指针往后扫，如果指的数原下标不在查询区间内就跳过，左边指的数小于右边的就左边指针跳，否则右边的一直跳，贡献是左边剩下的有效的数，具体细节看代码。
红色部分考虑我们前面记录的 \(cnt\mathtt{2}\) 也就是每个块中小于等于 \(x\) 的数的个数，块之间的前缀和。直接枚举左右散块的数然后对中间整块差分就行了。
但是毒瘤 \(\mathtt{lxl}\) 他妈就喜欢卡常，这代码是对的，但是思路和实现还是太繁琐了，之后有时间再来写吧。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define in inline
const ll N=100100,M=400;
struct xx{
ll val;
int id;
}b[N];
in bool cmp(xx x,xx y){
return x.val==y.val?x.id<y.id:x.val<y.val;
}
int n,m;
ll a[N];
int ns,nq,st[400],ed[400],bel[N];
ll sum1[400][400],sum2[400][N],sum3[400][N];
int sum[N];
//i~j整块贡献、每个块逆序对数前缀/后缀和
int cnt1[400][N];
ll cnt2[400][N];
int c[N];
//cnt1每个块内小于等于j的数的个数，cnt2是cnt1块间前缀和
in int lowbit(int x){return x&-x;}
in void update(int x,int k){
while(x<=n){
c[x]+=k;
x+=lowbit(x);
}
}
in int query(int x){
int ans=0;
while(x){
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int c1[350],c2[350];
in ll calc(ll l,ll r){
if(l>r) return 0ll;
ll ans=0; int lx=bel[l],rx=bel[r];
if(lx==rx){
ans=sum2[rx][r]-sum2[lx][l-1];
int t1=0,t2=0;
for(int i=st[lx];i<=ed[lx];++i)
if(b[i].id<l) c1[++t1]=b[i].val;
else if(b[i].id<=r) c2[++t2]=b[i].val;
for(int i=1,j=1;i<=t1;++i){
while(j<=t2&&c1[i]>c2[j]) ++j;
ans-=j-1;
}
return ans;
}
ans+=sum2[rx][r]+sum3[lx][l]; //散块内部贡献
int j=st[rx],i_cnt=0,i_n=ed[lx]-l+1;
for(int i=st[lx];i<=ed[lx];++i){ //散块之间贡献
if(b[i].id<l) continue;
++i_cnt;
while(j<=ed[rx]&&b[j].val<b[i].val){
if(b[j].id<=r) ans+=i_n-i_cnt+1;
++j;
}
}
if(rx>lx+1){
ll siz=ns*((rx-1)-(lx+1)+1);
for(int i=l;i<=ed[lx];++i) ans+=cnt2[rx-1][a[i]]-cnt2[lx][a[i]];
for(int i=st[rx];i<=r;++i) ans+=siz-(cnt2[rx-1][a[i]]-cnt2[lx][a[i]]); //整散之间贡献
}
if(rx>lx+1) ans+=sum1[lx+1][rx-1]; //整块贡献
return ans;
}
int main(){
n=read(),m=read(); ns=260,nq=ceil(n*1.0/ns);
for(int i=1;i<=n;++i) a[i]=read(),b[i]=(xx){a[i],i};
for(int i=1;i<=nq;++i){
st[i]=ns*(i-1)+1,ed[i]=min(ns*i,n);
for(int j=st[i];j<=ed[i];++j){
bel[j]=i;
update(a[j],1);
sum[j]=(j-st[i]+1)-query(a[j]);
sum2[i][j]=sum2[i][j-1]+sum[j];
//散块内部贡献，每个块内逆序对数前缀和
++cnt1[i][a[j]];
}
for(int j=1;j<=n;++j) cnt1[i][j]+=cnt1[i][j-1],cnt2[i][j]=cnt2[i-1][j]+cnt1[i][j];
for(int j=st[i];j<=ed[i];++j) update(a[j],-1);
sort(b+st[i],b+ed[i]+1,cmp);
}
for(int i=1;i<=nq;++i){
for(int j=i;j<=nq;++j){
for(int k=st[j];k<=ed[j];++k){
ll siz=ns*((j-1)-i+1);
sum1[i][j]+=siz-(cnt2[j-1][a[k]]-cnt2[i-1][a[k]]);
}
sum1[i][j]+=sum1[i][j-1]+sum2[j][ed[j]];
}
for(int j=ed[i];j>=st[i];--j) update(a[j],1),sum[j]=query(a[j]-1);
for(int j=ed[i];j>=st[i];--j) update(a[j],-1),sum3[i][j]=sum3[i][j+1]+sum[j];
}
ll las=0;
for(int i=1;i<=m;++i){
ll x,y;
x=read(),y=read();
x^=las,y^=las;
las=calc(x,y);
write(las),putchar('\n');
}
return 0;
}
但我还是想骂人，妈的这题想了两天写加调了两天半最后他妈被卡常，淦，再也不做傻逼卡常题了/fn
标签：int,ll,rx,二月,ans,散块,lx From： https://www.cnblogs.com/heshuwan/p/18002747