Code
Data Structures (Segment Tree)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=5e5;
const ll inf=1e18;
ll s[maxn+5];
struct tnode{
ll l,r;
ll lazy;
ll sum;
ll min,max,set;
};
struct segment_tree{
tnode t[4*maxn+5];
ll mp[maxn+5];//[i,i]->t[mp[i]]
void pushdown(ll root){
if(!(t[root].lazy==0 and t[root].set==-inf)){
if(t[root].lazy!=0){
t[root].sum+=t[root].lazy*(t[root].r-t[root].l+1);
t[root].max+=t[root].lazy;
t[root].min+=t[root].lazy;
}
if(t[root].set!=-inf){
t[root].sum=t[root].set*(t[root].r-t[root].l+1);
t[root].max=t[root].set;
t[root].min=t[root].set;
}
if(t[root].l!=t[root].r){
if(t[root].lazy!=0){
if(t[root*2].set!=-inf) t[root*2].set+=t[root].lazy;
else t[root*2].lazy+=t[root].lazy;
if(t[root*2+1].set!=-inf) t[root*2+1].set+=t[root].lazy;
else t[root*2+1].lazy+=t[root].lazy;
}
if(t[root].set!=-inf){
t[root*2].set=t[root].set;
t[root*2].lazy=0;
t[root*2+1].set=t[root].set;
t[root*2+1].lazy=0;
}
}
t[root].lazy=0;
t[root].set=-inf;
}
}
void pushup(ll root){//=update
pushdown(root*2),pushdown(root*2+1);
t[root].sum=t[root*2].sum+t[root*2+1].sum;
t[root].max=max(t[root*2].max,t[root*2+1].max);
t[root].min=min(t[root*2].min,t[root*2+1].min);
}
void build(ll root,ll l,ll r){//ini:(1,1,n)
t[root].l=l,t[root].r=r;
t[root].lazy=0;
t[root].set=-inf;
if(l==r){
t[root].sum=s[l];
t[root].min=s[l];
t[root].max=s[l];
mp[l]=root;
}
else{
ll mid=(l+r)/2;
build(root*2,l,mid),build(root*2+1,mid+1,r);
pushup(root);
}
}
ll sum(ll root,ll l,ll r){//sum_of:[l,r]
pushdown(root);
if(t[root].l>=l and t[root].r<=r){
return t[root].sum;
}
ll mid=(t[root].l+t[root].r)/2;
if(r<=mid) return sum(root*2,l,r);
else{
if(l>mid) return sum(root*2+1,l,r);
else return sum(root*2,l,mid)+sum(root*2+1,mid+1,r);//!with mod!
}
}
ll tmin(ll root,ll l,ll r){//min_of:[l,r]
pushdown(root);
if(t[root].l>=l and t[root].r<=r){
return t[root].min;
}
ll mid=(t[root].l+t[root].r)/2;
if(r<=mid) return tmin(root*2,l,r);
else{
if(l>mid) return tmin(root*2+1,l,r);
else return min(tmin(root*2,l,mid),tmin(root*2+1,mid+1,r));
}
}
ll tmax(ll root,ll l,ll r){//max_of:[l,r]
pushdown(root);
if(t[root].l>=l and t[root].r<=r){
return t[root].max;
}
ll mid=(t[root].l+t[root].r)/2;
if(r<=mid) return tmax(root*2,l,r);
else{
if(l>mid) return tmax(root*2+1,l,r);
else return max(tmax(root*2,l,mid),tmax(root*2+1,mid+1,r));
}
}
void change(ll root,ll l,ll r,ll val){//[l,r]+val
pushdown(root);
if(l==t[root].l and r==t[root].r){
t[root].lazy+=val;
return;
}
ll mid=(t[root].l+t[root].r)/2;
if(r<=mid) change(root*2,l,r,val);
else{
if(l>mid) change(root*2+1,l,r,val);
else{
change(root*2,l,mid,val),change(root*2+1,mid+1,r,val);
}
}
pushup(root);
}
void tset(ll root,ll l,ll r,ll val){//[l,r]=val
pushdown(root);
if(l==t[root].l and r==t[root].r){
t[root].set=val;
return;
}
ll mid=(t[root].l+t[root].r)/2;
if(r<=mid) tset(root*2,l,r,val);
else{
if(l>mid) tset(root*2+1,l,r,val);
else{
tset(root*2,l,mid,val),tset(root*2+1,mid+1,r,val);
}
}
pushup(root);
}
}T;
int main(){
ll n,m,i,j,k,a,b,c,d,op;
scanf("%lld%lld",&n,&m);
for(i=1;i<=n;i++) scanf("%lld",&s[i]);
T.build(1,1,n);
while(m--){
scanf("%lld",&op);
if(op<=2) scanf("%lld%lld%lld",&a,&b,&c);
else scanf("%lld%lld",&a,&b);
if(op==1) T.change(1,a,b,c);
if(op==2) T.tset(1,a,b,c);
if(op==3) printf("%lld\n",T.sum(1,a,b));
if(op==4) printf("%lld\n",T.tmax(1,a,b));
if(op==5) printf("%lld\n",T.tmin(1,a,b));
}
return 0;
}
Mathematics (extended Euclidean algorithm, modular exponentiation, Euler's totient function, extended Chinese remainder theorem)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b){
if(min(abs(a),abs(b))==0) return max(abs(a),abs(b));
return __gcd(abs(a),abs(b));
}
ll lcm(ll a,ll b){//only for: 1<=a,b<=1e9
return a*b/gcd(a,b);
}
ll exgcd(ll a,ll b,ll &x,ll &y){//ax+by=(a,b),ans:(x+k*b/(a,b),y-k*a/(a,b))
if(b==0) return x=1,y=0,a;//ax+by=d,ans:(x*d/(a,b)+k*b/(a,b),y*d/(a,b)-k*a/(a,b))
ll r=exgcd(b,a%b,y,x);//get x:mul first,mod second
y-=a/b*x;
return r;
}
ll ny(ll x,ll m){//x^-1(mod m)
if(gcd(x,m)!=1) return -1;
ll a,b;exgcd(x,m,a,b);
return (a%m+m)%m;
}
ll get_phi(ll n){//n=p1^a1+p2^a2+...+pn^an,phi(n)=(p1-1)*p1^(a1-1)+(p2-1)*p2^(a2-1)+...+(pn-1)*pn^(an-1)
ll i,phi=1;
for(i=2;i<=n/i;i++){
if(n%i==0){
phi*=i-1,n/=i;
while(n%i==0) phi*=i,n/=i;
}
}
if(n>1) phi*=n-1;
return phi;
}
const ll maxn=1e7;
bool not_prime[maxn+5];
ll prime[maxn/10+5],phi[maxn+5],tot=0;
void phi_euler_sieve(ll n){//calculate phi[1~n],O(n)
ll i,j,k;
for(i=2;i<=n;i++){
if(not_prime[i]==0) prime[++tot]=i,phi[i]=i-1;
for(j=1;j<=tot and i*prime[j]<=n;j++){
not_prime[i*prime[j]]=1;
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
ll inv[maxn+5];
void pre_ny(ll n,ll p){//O(n)
ll i,j,k;inv[1]=1;
for(i=2;i<=n;i++) inv[i]=(p-p/i)*(inv[p%i])%p;
}
const ll mod=1e9+7;
ll qmksm(ll a,ll b){//a^c=a^(c%phi(m)+phi(m)),mod m
ll sc=1,zc=a%mod;
while(b){
if(b&1) sc=(sc*zc)%mod;
b>>=1,zc=(zc*zc)%mod;
}
return sc;
}
ll ny(ll x){
return qmksm(x,mod-2);
}
const ll maxn2=1e5;
pair<ll,ll>p_crt[maxn2+5];
ll slow_mul(ll a,ll b,ll mod){
ll sc=0;
while(b>0){
if(b&1) sc=(sc+a)%mod;
a=(a+a)%mod,b/=2;
}
return sc;
}
ll excrt(ll n){//x=a(mod m),(a,m),lcm(m)<=1e18
ll i,j,x,y,k,a,b,c,M=p_crt[1].second,ans=p_crt[1].first,zc,bzc;
for(int i=2;i<=n;i++){
a=M,b=p_crt[i].second,c=(p_crt[i].first-ans%b+b)%b;
zc=exgcd(a,b,x,y),bzc=b/zc;
if(c%zc!=0) return -1;
x=slow_mul(x,c/zc,bzc);
ans+=x*M,M*=bzc,ans=(ans%M+M)%M;
}
return (ans%M+M)%M;
}
ll zhs(ll m,ll n){//m<=n,sc<=1e18
ll i,sc=1;
if(m>n) return 0;
for(i=n;i>=n-m+1;i--) sc*=i,sc/=n+1-i;
return sc;
}
/*ll zhs(ll m,ll n){//lukas
if(m>=mod or n>=mod) return zhs(m/mod,n/mod)*zhs(m%mod,n%mod)%mod;
if(m>n) return 0;
return jc[n]*jcn[m]%mod*jcn[n-m]%mod;
}*/
int main(){
return 0;
}
Mathematics (NTT)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353,G=3;
const ll maxn=5e6+5;
ll NTT_R[maxn+5],NTT_a[maxn+5],NTT_b[maxn+5],L=0,limit=1;
ll qmksm(ll a,ll b){
ll sc=1;
while(b>0){
if(b&1) sc=(sc*a)%mod;
a=(a*a)%mod,b>>=1;
}
return sc%mod;
}
ll ny(ll x){
return qmksm(x,mod-2);
}
void NTT(ll NTT_a[],ll type){
ll i,j,k,mid,wn,len,pos,w,x,y;
for(i=0;i<limit;i++) if(i<NTT_R[i]) swap(NTT_a[i],NTT_a[NTT_R[i]]);
for(mid=1;mid<limit;mid<<=1){
wn=qmksm(G,(mod-1)/(mid*2));
if(type==-1) wn=qmksm(wn,mod-2);
for(len=mid<<1,pos=0;pos<limit;pos+=len){
for(k=0,w=1;k<mid;k++,w=(w*wn)%mod){
x=NTT_a[pos+k],y=(w*NTT_a[pos+mid+k])%mod;
NTT_a[pos+k]=(x+y)%mod,NTT_a[pos+k+mid]=(x-y+mod)%mod;
}
}
}
if(type==-1){
ll limit_inv=ny(limit);
for(i=0;i<limit;i++) NTT_a[i]=(NTT_a[i]*limit_inv)%mod;
}
}
void poly_mul(ll NTT_a[],ll NTT_b[],ll deg){
ll i,j,k;
for(limit=1,L=0;limit<=deg;limit<<=1) L++;
for(i=0;i<limit;i++) NTT_R[i]=(NTT_R[i>>1]>>1)|((i&1)<<(L-1));
NTT(NTT_a,1),NTT(NTT_b,1);
for(i=0;i<limit;i++) NTT_a[i]=(NTT_a[i]*NTT_b[i])%mod;
NTT(NTT_a,-1);
}
ll A_NTTsr[maxn+5],B_NTTsr[maxn+5],NTTans[maxn+5];
void cal_NTT(ll n,ll m){
ll i,j,k;
for(i=0;i<=(n+m)<<1;i++) NTT_a[i]=NTT_b[i]=0;
for(i=0;i<=n;i++) NTT_a[i]=(A_NTTsr[i]%mod+mod)%mod;
for(i=0;i<=m;i++) NTT_b[i]=(B_NTTsr[i]%mod+mod)%mod;
poly_mul(NTT_a,NTT_b,n+m);
for(i=0;i<=n+m;i++) NTTans[i]=NTT_a[i];
}
int main(){
ll n,m,i,j,k;
scanf("%lld%lld",&n,&m);
for(i=0;i<=n;i++) scanf("%lld",&A_NTTsr[i]);
for(i=0;i<=m;i++) scanf("%lld",&B_NTTsr[i]);
cal_NTT(n,m);
for(i=0;i<=n+m;i++) printf("%lld ",NTTans[i]);
return 0;
}