网站开发佛山,建立企业网站的缺点,建设动漫网站的目的,代理注册公司流程和费用CF993E Nikita and Order Statistics
题意#xff1a;
给你一个数组 a1∼na_{1 \sim n}a1∼n#xff0c;对于 k0∼nk 0 \sim nk0∼n#xff0c;求出有多少个数组上的区间满足#xff1a;区间内恰好有 k 个数比 x 小。 x 为一个给定的数。 n≤2105n \le 2 \times 10^5n…CF993E Nikita and Order Statistics
题意
给你一个数组 a1∼na_{1 \sim n}a1∼n对于 k0∼nk 0 \sim nk0∼n求出有多少个数组上的区间满足区间内恰好有 k 个数比 x 小。 x 为一个给定的数。 n≤2×105n \le 2 \times 10^5n≤2×105 −1e9ai1e9-1e9a_i1e9−1e9ai1e9
题解
因为x是常数也就是说对于每个数只有贡献和无贡献之分 所以我们把所有大于等于X的数都改为0小于X的数都改为1这样原问题就转化为问有多少个连续序列满足和为k 用公式表示就是∑i1n∑j1n[ai−ajk]\sum_{i1}^n\sum_{j1}^n[a_i-a_jk]∑i1n∑j1n[ai−ajk] 设前缀和sumi∑j1iajsum_i\sum_{j1}^ia_jsumi∑j1iaj 再设Si∑[sumji],S00S_i\sum[sum_ji],S_00Si∑[sumji],S00,SiS_iSi就表示前缀和等于i的数量 原问题就变成求∑ik1nSi⋅Si−k\sum_{ik1}^nS_i⋅S_{i-k}ik1∑nSi⋅Si−k 比如k2时我们要查询区间和等于2的数量答案就是区间前缀和等于3的数量乘以区间和等于1的数量前缀和等于4的数量乘以前缀和等于2的数量…。因为前缀和等于3的减去前缀和等于1得到的这段区间一定是等于2的因此可以这样转化 这个式子看着愈发熟悉。。好像是卷积卷起来 ∑ik1nSi⋅Si−k∑i−jkSi⋅Sj∑ijkSi⋅S−j∑ijnkSi⋅Sn−j\sum_{ik1}^nS_i⋅S_{i-k}\sum_{i-jk}S_i⋅S_{j}\sum_{ijk}S_i⋅S_{-j}\sum_{ijnk}S_i⋅S_{n-j}ik1∑nSi⋅Si−ki−jk∑Si⋅Sjijk∑Si⋅S−jijnk∑Si⋅Sn−j 答案就是nk的系数k0时要特判
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const double PIacos(-1.0);
struct Complex{double x,y;Complex(double _x0.0,double _y0.0){x_x;y_y;}Complex operator -(const Complex b)const{return Complex(x-b.x,y-b.y);}Complex operator (const Complex b)const{return Complex(xb.x,yb.y);}Complex operator *(const Complex b)const{return Complex(x*b.x-y*b.y,x*b.yy*b.x);}
};
void change(Complex y[],int len)
{int i,j,k;for(i1,jlen/2;ilen-1;i){if(ij) swap(y[i],y[j]);klen/2;while(jk){j-k;k/2;}if(jk)jk;}
}
void fft(Complex y[],int len,int on)
{change(y,len);for(int h2;hlen;h1){Complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));for(int j0;jlen;jh){Complex w(1,0);for(int kj;kjh/2;k){Complex uy[k];Complex tw*y[kh/2];y[k]ut;y[kh/2]u-t;ww*wn;}}}if(on-1)for(int i0;ilen;i)y[i].x/len;
}
const int MAXN800010;
Complex x1[MAXN],x2[MAXN];
int str1[MAXN/2],str2[MAXN/2],a[MAXN];
ll sum[MAXN];
int _sum[MAXN];
int t,n,x;
int main()
{scanf(%d%d,n,x);memset(str1,0,sizeof str1);memset(str2,0,sizeof str2);str1[0]1;for(int i1;in;i){scanf(%d,a[i]);if(a[i]x)a[i]1;else a[i]0;_sum[i]_sum[i-1]a[i];str1[_sum[i]]1;}for(int i0;in;i){str2[i]str1[n-i];}int len1,len1n1,len2n1;while(lenlen1*2||lenlen2*2) len1;for(int i0;ilen1;i)x1[i]Complex(str1[i],0);for(int ilen1;ilen;i)x1[i]Complex(0,0);for(int i0;ilen2;i)x2[i]Complex(str2[i],0);for(int ilen2;ilen;i)x2[i]Complex(0,0);
// for(int i0;ilen;i){
// coutx2[i].x ;
// }
// coutendl;
// cout--endl;
// for(int i0;ilen;i){
// coutstr2[i] ;
// } coutendl;fft(x1,len,1);fft(x2,len,1);for(int i0;ilen;i)x1[i]x1[i]*x2[i];
// for(int i0;ilen;i)
// coutx1[i]x1[i].xendl;
// coutendl;fft(x1,len,-1);ll ans0,num0;for(int i1;in1;i){if(a[i]0i!n1)num;else {ansnum*(num1)/2;num0; } }coutans ;// coutendl;for(int i1;in;i){cout(ll)(x1[in].x0.5) ;}return 0;
}