CCPC 2023 北京市赛 G.【模板】线段树(线段树区间合并20次多项式)

2024-01-16 07:36

本文主要是介绍CCPC 2023 北京市赛 G.【模板】线段树(线段树区间合并20次多项式),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

思路来源

lyw

题解

洛谷高仿题目P4247

(ai+x)(ai+x)(ai+x)注意到当x有超过20项时,20个2相乘,对2的20次方取模就为0

所以,维护0次项到19次项乘积的和,向上合并时,是两个多项式卷积,这里暴力相乘即可

下推标记,当下放一个区间加x的标记时,a_{i}+=a_{j}*x^{j-i}*C_{j}^{j-i},其中,i<j<20

复杂度O(nlogn*20*20),比较卡常

经典卡常技巧:将取模改成unsigned int自然溢出即可

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef unsigned int ui;
typedef double db;
typedef pair<ll,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10,M=25,mod=(1<<20)-1;
int n,q;
ui b[N],C[M][M];
void add(ui &x,ui y){x+=y;
}
struct node{int l,r;ui c,p,a[21];node(){memset(a,0,sizeof a);c=0;}
}e[N*4];
struct segment{int n;#define l(x) e[x].l#define r(x) e[x].r#define c(x) e[x].cnode mer2(node &x,node &y){int ls=x.r-x.l+1,rs=y.r-y.l+1;node z;int w=min(ls+rs,20);z.a[w]=1;z.l=x.l,z.r=y.r;rep(i,0,ls){rep(j,0,rs){if(i+j>=w)break;ui v=x.a[i]*y.a[j];add(z.a[i+j],v);}}return z;}void up(int p){e[p]=mer2(e[p<<1],e[p<<1|1]);}void psd2(node &x,ui v){int len=x.r-x.l+1,sz=min(20,len);vector<ui>pw(sz+1,1);rep(i,1,sz)pw[i]=pw[i-1]*v;rep(i,0,sz-1){rep(j,i+1,sz){ui v=x.a[j]*pw[j-i]*C[j][j-i];add(x.a[i],v);}}}void psd(int p){if(c(p)){psd2(e[p<<1],c(p));add(c(p<<1),c(p));psd2(e[p<<1|1],c(p));add(c(p<<1|1),c(p));c(p)=0;}}void bld(int p,int l,int r){l(p)=l,r(p)=r,c(p)=0;if(l==r){e[p].a[0]=b[l];e[p].a[1]=1;return;}int mid=(l+r)/2;bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);up(p);}void init(int _n){n=_n;bld(1,1,n);}void upd(int p,int ql,int qr,ui x){if(ql<=l(p) && r(p)<=qr){psd2(e[p],x);add(c(p),x);return;}psd(p);int mid=(l(p)+r(p))/2;if(ql<=mid)upd(p<<1,ql,qr,x);if(qr>mid)upd(p<<1|1,ql,qr,x);up(p);}node ask(int p,int ql,int qr){if(ql<=l(p) && r(p)<=qr){return e[p];}psd(p);int mid=(l(p)+r(p))/2;if(ql<=mid && qr>mid){node L=ask(p<<1,ql,qr);node R=ask(p<<1|1,ql,qr);node res=mer2(L,R);return res;	}else if(ql<=mid){node L=ask(p<<1,ql,qr);return L;}else{node R=ask(p<<1|1,ql,qr);return R;}}
}seg;
void init(){C[0][0]=1;int up=21;rep(i,1,up){C[i][0]=C[i][i]=1;rep(j,1,i-1){C[i][j]=(C[i-1][j]+C[i-1][j-1]);}}
}
int op,l,r;
ui x;
int main(){init();sci(n),sci(q);rep(i,1,n)scanf("%u",&b[i]);seg.init(n);rep(i,1,q){scanf("%d%d%d",&op,&l,&r);if(op==1){scanf("%u",&x);seg.upd(1,l,r,x);}else{printf("%u\n",seg.ask(1,l,r).a[0]&mod);}}return 0;
}

这篇关于CCPC 2023 北京市赛 G.【模板】线段树(线段树区间合并20次多项式)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/611770

相关文章

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Python实现合并与拆分多个PDF文档中的指定页

《Python实现合并与拆分多个PDF文档中的指定页》这篇文章主要为大家详细介绍了如何使用Python实现将多个PDF文档中的指定页合并生成新的PDF以及拆分PDF,感兴趣的小伙伴可以参考一下... 安装所需要的库pip install PyPDF2 -i https://pypi.tuna.tsingh

使用Apache POI在Java中实现Excel单元格的合并

《使用ApachePOI在Java中实现Excel单元格的合并》在日常工作中,Excel是一个不可或缺的工具,尤其是在处理大量数据时,本文将介绍如何使用ApachePOI库在Java中实现Excel... 目录工具类介绍工具类代码调用示例依赖配置总结在日常工作中,Excel 是一个不可或缺的工http://

使用Python创建一个能够筛选文件的PDF合并工具

《使用Python创建一个能够筛选文件的PDF合并工具》这篇文章主要为大家详细介绍了如何使用Python创建一个能够筛选文件的PDF合并工具,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录背景主要功能全部代码代码解析1. 初始化 wx.Frame 窗口2. 创建工具栏3. 创建布局和界面控件4

Python自动化办公之合并多个Excel

《Python自动化办公之合并多个Excel》在日常的办公自动化工作中,尤其是处理大量数据时,合并多个Excel表格是一个常见且繁琐的任务,下面小编就来为大家介绍一下如何使用Python轻松实现合... 目录为什么选择 python 自动化目标使用 Python 合并多个 Excel 文件安装所需库示例代码

使用Python合并 Excel单元格指定行列或单元格范围

《使用Python合并Excel单元格指定行列或单元格范围》合并Excel单元格是Excel数据处理和表格设计中的一项常用操作,本文将介绍如何通过Python合并Excel中的指定行列或单... 目录python Excel库安装Python合并Excel 中的指定行Python合并Excel 中的指定列P

基于C#实现PDF文件合并工具

《基于C#实现PDF文件合并工具》这篇文章主要为大家详细介绍了如何基于C#实现一个简单的PDF文件合并工具,文中的示例代码简洁易懂,有需要的小伙伴可以跟随小编一起学习一下... 界面主要用于发票PDF文件的合并。经常出差要报销的很有用。代码using System;using System.Col

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

Python视频剪辑合并操作的实现示例

《Python视频剪辑合并操作的实现示例》很多人在创作视频时都需要进行剪辑,本文主要介绍了Python视频剪辑合并操作的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录介绍安装FFmpegWindowsMACOS安装MoviePy剪切视频合并视频转换视频结论介绍

不删数据还能合并磁盘? 让电脑C盘D盘合并并保留数据的技巧

《不删数据还能合并磁盘?让电脑C盘D盘合并并保留数据的技巧》在Windows操作系统中,合并C盘和D盘是一个相对复杂的任务,尤其是当你不希望删除其中的数据时,幸运的是,有几种方法可以实现这一目标且在... 在电脑生产时,制造商常为C盘分配较小的磁盘空间,以确保软件在运行过程中不会出现磁盘空间不足的问题。但在