当前位置: 首页 > news >正文

网站开发佛山建立企业网站的缺点

网站开发佛山,建立企业网站的缺点,建设动漫网站的目的,代理注册公司流程和费用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−1e9ai​1e9 题解 因为x是常数也就是说对于每个数只有贡献和无贡献之分 所以我们把所有大于等于X的数都改为0小于X的数都改为1这样原问题就转化为问有多少个连续序列满足和为k 用公式表示就是∑i1n∑j1n[ai−ajk]\sum_{i1}^n\sum_{j1}^n[a_i-a_jk]∑i1n​∑j1n​[ai​−aj​k] 设前缀和sumi∑j1iajsum_i\sum_{j1}^ia_jsumi​∑j1i​aj​ 再设Si∑[sumji],S00S_i\sum[sum_ji],S_00Si​∑[sumj​i],S0​0,SiS_iSi​就表示前缀和等于i的数量 原问题就变成求∑ik1nSi⋅Si−k\sum_{ik1}^nS_i⋅S_{i-k}ik1∑n​Si​⋅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∑n​Si​⋅Si−k​i−jk∑​Si​⋅Sj​ijk∑​Si​⋅S−j​ijnk∑​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; }
http://wiki.neutronadmin.com/news/188953/

相关文章:

  • 广州网络建站网站开发一般多钱
  • 微信怎么做一些微网站建筑工程招聘最新信息平台
  • 照明灯具类企业网站58同城做网站被骗
  • 鹤壁做网站哪家好京东联盟的网站怎么做的
  • 乐平市网站建设秦皇岛新闻最新消息
  • 邯郸网站建设开发公司深圳做网站哪家专业
  • 做网站如何寻找客源建设公司简介怎么写
  • 音乐网站的建设网站建设php带数据库模板
  • 网页设计与网站建设ppt有没有专门做旅游攻略的网站
  • 大学生可以做的网站项目在线观看网址最新电影
  • 关于集团网站建设的卢镇seo网站优化排名
  • 百度云做网站有优势吗网站服务器选择
  • 淮南市住房与城乡建设部网站花生壳域名做网站
  • 企业网站建设的一般原则个人网站制作模板响应式
  • 哪里有免费的网站模板下载 迅雷下载软件wordpress 网页排版
  • 科技网站欣赏免费ftp转换wordpress
  • 自己怎么做网址开网站网页制作三剑客不包括
  • 网站全屏视频怎么做美丽说网站模板
  • 广东网站建设商家高端网站建设设计公司
  • 提高网站权重工具wordpress添加分享
  • 有偿做设计的网站如何下载别人的网站模板
  • 域名里可以建网站首次建设网站流程
  • 内蒙古城乡住房建设厅网站html链接文字颜色
  • 温州市网站优化代理备案 网站 安全吗
  • 推荐几个网站图片网站安康市天然气公司
  • 扬中网站建设好么学校网站制作代码
  • 网站怎么开通微信支付基于wordpress的开发
  • 产品网站开发常州网络优化排名
  • wordpress js 页脚佛山市seo推广
  • 哪有做奇石网站wordpress inc目录