题解：P6579 [Ynoi2019] Happy Sugar Life
Purslane
·
·
题解
Solution
唉分享一下我的做法，可能比较麻烦。不过确实好想。
这种题只需要想到分块可能就做完了。 /kel
把 (i,p_i) 描到二维平面上，问的就是一个矩形里包含了多少个上升二元对。
4-side 矩形不好处理，考虑拆成 2-side 矩形，如图所示：
一个 2-side 矩形里面包含多少个上升对是容易计算的，跑两边二维数点就行。
容斥一遍之后，只有形如 CC、CA、CD、CB 的二元组还存在。
接着考虑 3-side 矩形能给我们带来什么。比如用 $CA$ 构成的 3-side 矩形的答案，减去 A 构成的 3-side 矩形的答案，得到的是 $CA+CC$。同理我们可以得到 $CD+CC$。而 $(CA+CC)+(CD+CC)-(CA+CD+CC) = CC$，也就是我们会做 3-side 矩形这道题就结束了。不妨只考虑向纵轴正方向开口的矩形。
套路的进行分块。考虑进行**扫描线**，按照纵坐标（$y$）从大王小加入点，然后询问一个区间内的上升对个数。
不就这几种贡献吗：
1. 整块内。加入一个点之后，暴力在块内将和它有关的上升二元组加入即可。维护当前前 $i$ 个块里有多少个数 $cnt$，后面要用到。
2. 整块间。记二元组 $(i,j)$ 表示第 $i$ 个块到第 $j$ 个块的答案。发现新增一个数，会进行 $O(\sqrt n)$ 次对 $i \le L$，$j = R$ 的二元组 $(i,j)$ 整体加上一个相同的值。（有一个非常重要的事实：我们每次加入的都是**当前区间的最小数**，所以只需要考虑右边比他大的）新增的这个量可以用 $cnt$ 算出。
3. 散块内部。需要知道当前一个块内前缀或后缀的上升二元组个数。这个每次修改也只会影响 $O(\sqrt n)$ 个位置的值，暴力算一遍就行。
4. 散块之间。由于块内相对顺序不会改变，所以排好序之后归并一下就行。特别地，对于询问在同一个块内的情况，用两个前缀之差减去归并的结果。
5. 散块和整块。对于整块左边的位置而言，在它加入的时候算一下整块有多少个数；对于整块右边的位置而言，它加入的时候算一下整块有多少个数，然后在询问的时候再算一下整块有多少个数，作差即得贡献。
这样可以做到线性空间，$O(m \sqrt n)$ 的复杂度。稍微调一下块长就可以过这个题，当然无压力通过时代的眼泪。
不用太多 vector 就能过。
代码（有点丑。。）
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,m,p[MAXN],X1[MAXN],X2[MAXN],Y1[MAXN],Y2[MAXN],rev[MAXN];
ll ans[MAXN],tcnt[MAXN],tcnt1[MAXN],tcnt2[MAXN];
struct QR1 {int id,y,op;};
vector<QR1> qr1[MAXN];
ll tr[MAXN];
inline void update(int pos,const int v) {pos=n-pos+1;while(pos<=n) tr[pos]+=v,pos+=pos&-pos;return ;}
inline ll query(int pos) {ll ans=0;pos=n-pos+1;while(pos) ans+=tr[pos],pos-=pos&-pos;return ans;}
struct QR2 {int l,r,id;};
const int B=300,BB=B+10;
int L[MAXN],R[MAXN],bel[MAXN],k,pre[MAXN],suf[MAXN],cnt[MAXN],ins[MAXN]; //pre 表示前缀，suf 表示后缀，
ll add[MAXN/B][MAXN/B];
int tmtp[MAXN],st[MAXN/B][BB],len[MAXN/B];
pair<int,QR2> qr2[MAXN*2];
struct QR3 {int l,r,y,yy,id;};
int etot,mtot;
pair<int,QR3> ex[MAXN*2];
inline void add_pos(const int pos,const int val) {
int bl=bel[pos],tmp=0;
ffor(j,bl,k) cnt[j]++,add[bl][j]+=cnt[j]-cnt[bl];
ffor(j,pos+1,R[bl]) {if(p[j]>val) ins[bl]++,tmp++;pre[j]+=tmp;}
roff(j,pos,L[bl]) suf[j]+=tmp;
return ;
}
inline int calc(const int l1,const int r1,const int l2,const int r2,const int val) {
int pos=0,ans=0,cnt=0;
ffor(i,1,len[bel[l2]]) {
int id=st[bel[l2]][i];
if(l2<=id&&id<=r2&&p[id]>=val) {
while(pos<len[bel[l1]]) {
int idx=st[bel[l1]][pos+1];
if(p[idx]>p[id]) break ;
if(l1<=idx&&idx<=r1&&p[idx]>=val) cnt++;
pos++;
}
ans+=cnt;
}
}
return ans;
}
int ss[MAXN],ee[MAXN];
void I_AK_NOI2020_Day1(void) {
ffor(i,1,n) rev[p[i]]=i;
k=(n+B-1)/B;
ffor(i,1,k) L[i]=R[i-1]+1,R[i]=min(n,i*B);
ffor(i,1,k) {
len[i]=0;
ffor(j,L[i],R[i]) bel[j]=i,tmtp[++len[i]]=j;
sort(tmtp+1,tmtp+len[i]+1,[&](int A,int B) {return p[A]<p[B];});
ffor(j,1,len[i]) st[i][j]=tmtp[j];
}
etot=mtot=0;
ffor(i,1,m) {
qr2[++mtot]={Y1[i],{X1[i],X2[i],i}},qr2[++mtot]={Y2[i]+1,{X1[i],X2[i],-i}};
if(bel[X1[i]]!=bel[X2[i]]) ex[++etot]={X1[i],{X1[i],X2[i],Y1[i],Y2[i]+1,i}},ex[++etot]={X2[i]+n,{X1[i],X2[i],Y1[i],Y2[i]+1,i}};
}
sort(qr2+1,qr2+mtot+1,[](pair<int,QR2> A,pair<int,QR2> B) {return A.first<B.first;});
sort(ex+1,ex+etot+1,[](pair<int,QR3> A,pair<int,QR3> B) {return A.first<B.first;});
memset(ss,0x3f,sizeof(ss)),memset(ee,0,sizeof(ee));
ffor(i,1,etot) {
ss[ex[i].first]=min(ss[ex[i].first],i);
ee[ex[i].first]=i;
}
ffor(i,1,n+n) ee[i]=max(ee[i],ee[i-1]);
roff(i,n+n,1) ss[i]=min(ss[i],ss[i+1]);
while(mtot&&qr2[mtot].first>n) mtot--;
roff(i,n,1) {
add_pos(rev[i],i);
while(mtot&&qr2[mtot].first==i) {
auto pr=qr2[mtot].second; mtot--;
int l=pr.l,r=pr.r,id=pr.id;
if(bel[l]==bel[r]) {
int ad=pre[r];
if(l!=L[bel[l]]) ad-=pre[l-1];
ad-=calc(L[bel[l]],l-1,l,r,i);
if(id>0) ans[id]+=ad;
else ans[-id]-=ad;
}
else {
int lid=bel[l]+1,rid=bel[r]-1;
ll ad=0;
if(lid<=rid) ffor(j,lid,rid) ad+=add[j][rid]+ins[j];
ad+=calc(l,R[bel[l]],L[bel[r]],r,i)+suf[l]+pre[r];
int mzx=cnt[rid]-cnt[lid-1];
ffor(j,L[bel[r]],r) if(p[j]>=i) ad+=mzx;
if(id>0) ans[id]+=ad;
else ans[-id]-=ad;
}
}
int pos=rev[i];
ffor(j,ss[L[bel[pos]]],ee[pos]) {
auto pr=ex[j].second;
if(pr.y<=i&&pr.yy>i) {
int id=pr.id,lid=bel[pos]+1,rid=bel[pr.r]-1;
ans[id]+=cnt[rid]-cnt[lid-1];
}
}
ffor(j,ss[pos+n],ee[R[bel[pos]]+n]) {
auto pr=ex[j].second;
if(pr.y<=i&&pr.yy>i) {
int id=pr.id,lid=bel[pr.l]+1,rid=bel[pos]-1;
ans[id]-=cnt[rid]-cnt[lid-1];
}
}
}
return ;
}
int main() {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
ffor(i,1,n) cin>>p[i];
ffor(i,1,m) cin>>X1[i]>>X2[i]>>Y1[i]>>Y2[i],qr1[X1[i]].push_back({i,Y1[i],1}),qr1[X1[i]].push_back({i,Y2[i]+1,2}),qr1[X2[i]+1].push_back({i,Y1[i],2}),qr1[X2[i]+1].push_back({i,Y2[i]+1,3});
roff(i,n,1) {
tcnt[i]=query(p[i]),update(p[i],1);
for(auto qr:qr1[i])
if(qr.op==1) tcnt1[qr.id]+=query(qr.y);
else if(qr.op==2) tcnt1[qr.id]-=query(qr.y);
else tcnt1[qr.id]+=query(qr.y),tcnt2[qr.id]=query(qr.y);
}
ffor(i,1,m) ans[i]=-tcnt1[i]*tcnt2[i];
memset(tr,0,sizeof(tr));
roff(i,n,1) {
update(p[i],tcnt[i]);
for(auto qr:qr1[i])
if(qr.op==1||qr.op==3) ans[qr.id]+=query(qr.y);
else ans[qr.id]-=query(qr.y);
}
ffor(i,1,m) ans[i]=-ans[i];
I_AK_NOI2020_Day1();
memset(pre,0,sizeof(pre)),memset(suf,0,sizeof(suf)),memset(add,0,sizeof(add)),memset(cnt,0,sizeof(cnt)),memset(ins,0,sizeof(ins));
ffor(i,1,n) rev[p[i]]=i;
ffor(i,1,n) p[i]=rev[i];
ffor(i,1,m) swap(X1[i],Y1[i]),swap(X2[i],Y2[i]);
I_AK_NOI2020_Day1();
ffor(i,1,m) cout<<ans[i]<<'\n';
return 0;
}
```