题解：P15839 [蓝桥杯第一届国际赛] 莲蓬池

· · 题解

题目解析

解题方法

本题解 A_i 代表横坐标，纵坐标同理。

把题目形式化一下，给你一个区间 [l,r]，求 \sum_{i=l}^{r} \sum_{j=l}^{i-1} |A_i-A_j|，不能重复计算贡献。

计算中出现绝对值就很难算，我们转换一下，对于每个 l \le j < i 的 j，实际上分两种情况：

整理一下，设 $cnt(x)$ 表示满足 $x$ 的数量，对于任意一个 $l \le i \le r$ 的 $i$，该位置的答案是： $cnt(A_i\ge A_j) \times A_i - \sum_{A_i \ge A_j} A_j +\sum_{A_i < A_j} A_j- cnt(A_i< A_j) \times A_i$，其中需要保证 $l \le j <i$。 维护这个的方法很简单，外面是莫队维护区间查询，注意加入的顺序其实是无所谓的，到最后答案是一样的，因此可以用莫队修改顺序优化时间。 里面套树状数组，分别维护：横坐标小于等于任意一个数的个数，横坐标小于等于任意一个数的数字和。 树状数组的维护过程：横坐标小于等于任意一个数的个数维护时，只需要在添加每一个数字 $x$ 时，将位置是 $x$ 的位置 $+1$，查询大于此的位置用总数减即可。查询横坐标小于等于任意一个数的数字和时，添加每一个数字 $x$ 时在位置是 $x$ 的位置 $+x$，查询方式和上面相同。 ### 卡常技巧 感谢 @xubaichuan 让我卡常成功。 这道题卡常，需要我们优化。 首先，尽量避免 `vector`。其次，相同坐标的信息用同一个树状数组，树状数组内部用两个数组维护两个信息。 尽量减少树状数组的运算，能存起来下次用就用。 使用 `inline` 加速。 ## 正解代码 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int px[200005]; int py[200005]; int ans[200005]; int bi[200005]; int sumx=0,sumy=0,sz=0; int v[200005]; int most=0,lena=0; //Linux 评测机是xxx_unlocked //Windows 要去掉_unlocked inline void read(int& x) { x=0; char ch=getchar_unlocked(); bool flag=false; while(ch<'0' || ch>'9') { if(ch=='-') flag=1; ch=getchar_unlocked(); } while(ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar_unlocked(); } if(flag) x=-x; } inline void write(int x) { if(x<0) { putchar_unlocked('-'); x=-x; } if(x>9) write(x/10); putchar_unlocked(x%10+'0'); } class BIT { private: #define lowbit(x) x&-x; public: int n; int t[400005]; int c[400005]; BIT(int sz) { n=sz; } BIT(){} inline void add(int id,int k,int sign) //加入一个数字 { while(id<=n) { t[id]+=k;c[id]+=sign; id+=lowbit(id); } } inline pair<int,int> query(int l,int id) //查询前缀和 { int ans=0,cnt=0; while(id>=1) { ans+=t[id];cnt+=c[id]; id-=lowbit(id); } return make_pair(ans,cnt); } }; struct query { int l,r,id; inline query(int _l,int _r,int _id) { l=_l,r=_r,id=_id; } query(void){} inline friend bool operator<(query a,query b) { if(bi[a.l]==bi[b.l]) { if(bi[a.l]&1) return a.r<b.r; else return a.r>b.r; } return bi[a.l]<bi[b.l]; } }q[200005]; BIT tx(400005);//维护 x 坐标信息 BIT ty(400005);//维护 y 坐标信息 inline void add(int x) { pair<int,int> xans=tx.query(-INT_MAX,px[x]); pair<int,int> yans=ty.query(-INT_MAX,py[x]); int lx=xans.first,ly=yans.first; int cx=xans.second,cy=yans.second; most+=-lx+cx*v[px[x]]; most+=(sumx-lx)-(sz-cx)*v[px[x]]; most+=-ly+cy*v[py[x]]; most+=(sumy-ly)-(sz-cy)*v[py[x]]; tx.add(px[x],v[px[x]],1); ty.add(py[x],v[py[x]],1);} inline void del(int x) { tx.add(px[x],-v[px[x]],-1); ty.add(py[x],-v[py[x]],-1); pair<int,int> xans=tx.query(-INT_MAX,px[x]); pair<int,int> yans=ty.query(-INT_MAX,py[x]); int lx=xans.first,ly=yans.first; int cx=xans.second,cy=yans.second; most-=-lx+cx*v[px[x]]; most-=(sumx-lx)-(sz-cx)*v[px[x]]; most-=-ly+cy*v[py[x]]; most-=(sumy-ly)-(sz-cy)*v[py[x]]; } signed main() { int n,m; read(n);read(m); lena=sqrt(n); for(int i=1;i<=n;i++) { bi[i]=(i-1)/lena+1; } int cntv=0; for(int i=1;i<=n;i++) { read(px[i]);read(py[i]); v[cntv++]=px[i]; v[cntv++]=py[i]; } v[cntv++]=-INT_MAX; sort(v,v+cntv); for(int i=1;i<=n;i++) { px[i]=lower_bound(v,v+cntv,px[i])-v; py[i]=lower_bound(v,v+cntv,py[i])-v; } for(int i=1;i<=m;i++) { read(q[i].l);read(q[i].r); q[i].id=i; } sort(q+1,q+1+m); int l=1,r=0; for(int i=1;i<=m;i++) { int ql=q[i].l,qr=q[i].r; while(l>ql) { add(--l),sz++,sumx+=v[px[l]],sumy+=v[py[l]]; } while(r<qr) { add(++r),sz++,sumx+=v[px[r]],sumy+=v[py[r]]; } while(r>qr) { sz--,sumx-=v[px[r]],sumy-=v[py[r]],del(r--); } while(l<ql) { sz--,sumx-=v[px[l]],sumy-=v[py[l]],del(l++); } ans[q[i].id]=most; } for(int i=1;i<=m;i++) { write(ans[i]); putchar_unlocked('\n'); } return 0; } ```