建设视频网站要求,做企业策划的公司,html教学,谷歌外贸题目大意
给你一个排列 p p p#xff0c;对于每一个 i i i#xff0c;我们在平面上#xff0c;放置一个点 ( i , p i ) (i,p_i) (i,pi)。对于坐标上下限都在 1 ∼ n 1\sim n 1∼n内的全体 ( n ( n 1 ) 2 ) 2 (\frac{n(n1)}{2})^2 (2n(n1))2矩形#xff0c;求每个矩形…题目大意
给你一个排列 p p p对于每一个 i i i我们在平面上放置一个点 ( i , p i ) (i,p_i) (i,pi)。对于坐标上下限都在 1 ∼ n 1\sim n 1∼n内的全体 ( n ( n 1 ) 2 ) 2 (\frac{n(n1)}{2})^2 (2n(n1))2矩形求每个矩形内部点数的 k k k次方之和。
形式化地请你计算 ∑ 1 ≤ l ≤ r ≤ n ∑ 1 ≤ d ≤ u ≤ n ∣ { i ∣ l ≤ i ≤ r ∨ d ≤ p i ≤ u } ∣ \sum\limits_{1\leq l\leq r\leq n}\sum\limits_{1\leq d\leq u\leq n}|\{i|l\leq i\leq r\vee d\leq p_i\leq u\}| 1≤l≤r≤n∑1≤d≤u≤n∑∣{i∣l≤i≤r∨d≤pi≤u}∣ 1 ≤ n ≤ 1 0 5 , 1 ≤ k ≤ 3 1\leq n\leq 10^5,1\leq k\leq 3 1≤n≤105,1≤k≤3 题解
我们可以考虑拆贡献点数的 k k k次方可以看成选 k k k个点的方案的线性组合。
什么意思呢就是在这 n n n个点中有序地可重地选择 k k k个点将所有包含这 k k k个点的矩形的贡献 1 1 1注意所有从 n n n个点中有序地可重地选 k k k个点的方案都要被计算贡献。
为什么可以这样呢对于每个矩形设这个矩形内的点数为 t t t在这个矩形中有序地可重地选 k k k个点的方案数为 t k t^k tk也就是说这个矩形在上面计算贡献的时候将贡献加了 t k t^k tk次一。
下面我们来求 k k k为不同的值时的答案。
当 k 1 k1 k1时
对每个点 ( x , p x ) (x,p_x) (x,px)答案的贡献增加 x × ( n − x 1 ) × p x × ( n − p x 1 ) x\times (n-x1)\times p_x\times (n-p_x1) x×(n−x1)×px×(n−px1)。
当 k 2 k2 k2时
我们考虑选的两个点相同的情况和两个点不同的情况。
对于两个点相同的情况这其实就是 k 1 k1 k1的情况每种情况会被算一次。
对于两个点不同的情况我们可以分为顺序对和逆序对来考虑
对于顺序对 x y , p x p y xy,p_xp_y xy,pxpy其贡献为 x × p x × ( n − y 1 ) × ( n − p y 1 ) x\times p_x\times (n-y1)\times (n-p_y1) x×px×(n−y1)×(n−py1)将 x × p x x\times p_x x×px存入树状数组中再用 ( n − y 1 ) × ( n − p y 1 ) (n-y1)\times (n-p_y1) (n−y1)×(n−py1)来乘即可对于逆序对 x y , p x p y xy,p_xp_y xy,pxpy将排列翻转之后按顺序对的方法来做即可
因为选点是有序的每种顺序对和逆序对都用两种选法被选到所以两个点不同的情况的贡献要乘 2 2 2。
当 k 3 k3 k3时
将 k 1 k1 k1的贡献计算一次三次选择同一个点 k 2 k2 k2的贡献计算两次三次选择两个不同的点下面再考虑三次选择三个不同的点的贡献。
分为两种本质不同的情况
情况1
------
|* |
| * |
| * |
------这种情况出现了 2 2 2次按 i i i左右翻转总共有 2 2 2次用两个树状数组维护即可。
情况2
------
| * |
|* |
| * |
------这种情况总共出现了 4 4 4次按 i i i左右翻转按 p i p_i pi上下翻转四个角度各一次总共有 4 4 4次用线段树来维护即可。可以在加入第一个点时直接在对应位置上加数在加入第二个点时将其后缀乘上对应的数再加入第三个点时查询前缀和。
因为选点是有序的每种顺序对和逆序对都用六种选法被选到所以两个点不同的情况的贡献要乘 6 6 6。
时间复杂度为 O ( n log n ) O(n\log n) O(nlogn)。
code
#includebits/stdc.h
#define lc k1
#define rc k1|1
using namespace std;
const long long mod998244353;
int n,K,p[100005];
long long tr1[100005],tr2[100005];
long long s[500005],hv[500005],ly[500005];
int lb(int i){return i(-i);
}
void pt1(int i,long long v){while(in){tr1[i](tr1[i]v)%mod;ilb(i);}
}
long long find1(int i){long long re0;while(i){re(retr1[i])%mod;i-lb(i);}return re;
}
void pt2(int i,long long v){while(in){tr2[i](tr2[i]v)%mod;ilb(i);}
}
long long find2(int i){long long re0;while(i){re(retr2[i])%mod;i-lb(i);}return re;
}
void build(int k,int l,int r){s[k]hv[k]ly[k]0;if(lr) return;int midlr1;build(lc,l,mid);build(rc,mid1,r);
}
void down(int k){s[lc](s[lc]hv[lc]*ly[k])%mod;s[rc](s[rc]hv[rc]*ly[k])%mod;ly[lc](ly[lc]ly[k])%mod;ly[rc](ly[rc]ly[k])%mod;ly[k]0;
}
void ch(int k,int l,int r,int x,long long y){if(lrlx){hv[k]y;s[k]ly[k]0;return;}if(ly[k]) down(k);int midlr1;if(xmid) ch(lc,l,mid,x,y);else ch(rc,mid1,r,x,y);hv[k](hv[lc]hv[rc])%mod;s[k](s[lc]s[rc])%mod;
}
void ts(int k,int l,int r,int x,int y,long long v){if(lxry){ly[k](ly[k]v)%mod;s[k](s[k]v*hv[k])%mod;return;}if(ly[k]) down(k);int midlr1;if(xmid) ts(lc,l,mid,x,y,v);if(ymid) ts(rc,mid1,r,x,y,v);s[k](s[lc]s[rc])%mod;
}
long long find(int k,int l,int r,int x,int y){if(lxry) return s[k];if(ly[k]) down(k);int midlr1;long long re0;if(xmid) re(refind(lc,l,mid,x,y))%mod;if(ymid) re(refind(rc,mid1,r,x,y))%mod;return re;
}
long long gt(){long long re0;build(1,1,n);for(int i1;in;i){re(refind(1,1,n,1,p[i])*(n-i1)%mod*(n-p[i]1)%mod)%mod;ts(1,1,n,p[i],n,p[i]);ch(1,1,n,p[i],i);}return re;
}
long long gt1(){long long re0;for(int i1;in;i){re(re1ll*i*(n-i1)%mod*p[i]%mod*(n-p[i]1)%mod)%mod;}return re;
}
long long gt2(){long long re0;for(int i1;in;i){re(refind1(p[i])*(n-i1)%mod*(n-p[i]1)%mod)%mod;pt1(p[i],1ll*i*p[i]%mod);}for(int i1;in;i){tr1[i]0;if(in-i1) swap(p[i],p[n-i1]);}for(int i1;in;i){re(refind1(p[i])*(n-i1)%mod*(n-p[i]1)%mod)%mod;pt1(p[i],1ll*i*p[i]%mod);}for(int i1;in;i){tr1[i]0;if(in-i1) swap(p[i],p[n-i1]);}return re;
}
long long gt3(){long long re0;for(int i1;in;i){long long nowfind1(p[i]);pt1(p[i],1ll*i*p[i]%mod);re(refind2(p[i])*(n-i1)%mod*(n-p[i]1)%mod)%mod;pt2(p[i],now);}for(int i1;in;i){tr1[i]tr2[i]0;if(in-i1) swap(p[i],p[n-i1]);}for(int i1;in;i){long long nowfind1(p[i]);pt1(p[i],1ll*i*p[i]%mod);re(refind2(p[i])*(n-i1)%mod*(n-p[i]1)%mod)%mod;pt2(p[i],now);}for(int i1;in;i){tr1[i]tr2[i]0;if(in-i1) swap(p[i],p[n-i1]);}re(regt())%mod;for(int i1;in;i)if(in-i1) swap(p[i],p[n-i1]);re(regt())%mod;for(int i1;in;i)p[i]n-p[i]1;re(regt())%mod;for(int i1;in;i)if(in-i1) swap(p[i],p[n-i1]);re(regt())%mod;return re;
}
int main()
{freopen(points.in,r,stdin);freopen(points.out,w,stdout);scanf(%d%d,n,K);for(int i1;in;i){scanf(%d,p[i]);}if(K1) printf(%lld,gt1());else if(K2) printf(%lld,(gt1()2*gt2())%mod);else{printf(%lld,(gt1()6*gt2()6*gt3())%mod);}return 0;
}
