【模板】汇总
\color{#F39C11}{普及-}
P1177 【模板】排序
#include<bits/stdc++.h>
using namespace std;
int a[1000010];
void change(int l,int r){
if(l>=r) return;
int i=l,j=r,mid=a[(l+r)/2];
while(i<j){
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j){
swap(a[i],a[j]);
i++;
j--;
}
}
change(l,j);
change(i,r);
}
int main(){
int n;
cin>>n;
for(int s=1;s<=n;s++) cin>>a[s];
change(1,n);
for(int s=1;s<=n;s++) cout<<a[s]<<' ';
return 0;
}P1226 【模板】快速幂
#include<bits/stdc++.h>
using namespace std;
long long a,b,p;
long long f(){
long long ans=1;
while(b){
if(b&1) ans*=a;
ans%=p;
a*=a;
a%=p;
b>>=1;
}
return ans;
}
int main(){
cin>>a>>b>>p;
cout<<a<<'^'<<b<<" mod "<<p<<'=';
cout<<f();
return 0;
}P3370 【模板】字符串哈希
#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int nm=1e8+30,b1=11111,b2=13131,p1=1e8+29,p2=1e8+17;
int n,ans;
bool vis[nm];
string s;
signed main(){
st();
cin>>n;
while(n--){
cin>>s;
int a=0,b=0;
for(int i=0;i<s.length();i++){
a=(a*b1+s[i])%p1;
b=(b*b2+s[i])%p2;
}
if(!vis[a]||!vis[b]){
vis[a]=vis[b]=1;
ans++;
}
}
cout<<ans;
return 0;
}
P3383 【模板】线性筛素数
#include<bits/stdc++.h>
using namespace std;
int a[10000005],n,m[100000005],top,q;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=2;i<=n;i++){
if(m[i]==0) a[++top]=i;
for(int k=1;k*i<=n&&a[k]*i<=n;k++){
m[a[k]*i]=1;
if(i%a[k]==0) break;
}
}
for(int i=1;i<=q;i++) cin>>m[i];
for(int i=1;i<=q;i++) cout<<a[m[i]]<<"\n";
return 0;
}B3614 【模板】栈
#include<bits/stdc++.h>
using namespace std;
unsigned long long T,n,x,a[100000005],top;
string cinn;
int main(){
cin>>T;
for(int i=1;i<=T;i++){
a[100000005]={};
top=0;
cin>>n;
for(int j=1;j<=n;j++){
cin>>cinn;
if(cinn=="push"){
cin>>x;
a[++top]=x;
}
if(cinn=="pop"){
if(top>0) top--;
else cout<<"Empty\n";
}
if(cinn=="query"){
if(top>0) cout<<a[top]<<endl;
else cout<<"Anguei!\n";
}
if(cinn=="size") cout<<top<<endl;
}
}
return 0;
}B3616 【模板】队列
#include<bits/stdc++.h>
using namespace std;
unsigned long long n,m,x,a[100000005],head,tail;
string cinn;
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
cin>>m;
if(m==1) {
cin>>x;
a[++tail]=x;
}
if(m==2) {
if(head<tail) head++;
else cout<<"ERR_CANNOT_POP\n";
}
if(m==3) {
if(head<tail) cout<<a[head+1]<<endl;
else cout<<"ERR_CANNOT_QUERY\n";
}
if(m==4) cout<<tail-head<<endl;
}
return 0;
}B3656 【模板】双端队列 1
#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int nm=1e6+10;
int n,m,k,ans,a,x;
list<int> q[nm];
string s;
signed main(){
st();
cin>>n;
while(n--){
cin>>s>>a;
if(s=="push_back"){
cin>>x;
q[a].push_back(x);
}
if(s=="pop_back"&&q[a].size()) q[a].pop_back();
if(s=="push_front"){
cin>>x;
q[a].push_front(x);
}
if(s=="pop_front"&&q[a].size()) q[a].pop_front();
if(s=="size") cout<<q[a].size()<<'\n';
if(s=="front"&&q[a].size()) cout<<q[a].front()<<'\n';
if(s=="back"&&q[a].size()) cout<<q[a].back()<<'\n';
}
return 0;
}P10815【模板】快速读入
#include<bits/stdc++.h>
using namespace std;
int f(){
int sum=0,flag=1;
char c=getchar_unlocked();
while(c<'0'||c>'9'){
if(c=='-') flag=-1;
c=getchar_unlocked();
}
while(c>='0'&&c<='9'){
sum=sum*10+c-'0';
c=getchar_unlocked();
}
return sum*flag;
}
void out(int x){
if(x<0){
putchar('-');
x=-x;
}
if(x<10) putchar(x+'0');
else{
out(x/10);
putchar(x%10+'0');
}
}
int main(){
int n=f(),sum=0;
while(n--) sum+=f();
out(sum);
return 0;
}\color{#FFC116}{普及/提高−}
P1883 【模板】三分 | 函数
#include<bits/stdc++.h>
using namespace std;
int n,a[10005],b[10005],d[10005],T;
double g(double x){
double m=-1e9;
for(int i=1;i<=n;i++){
m=max(m,a[i]*x*x+b[i]*x+d[i]);
}
return m;
}
double f() {
double l=0,r=1000;
while(r-l>=1e-9) {
double mid1=l+(r-l)/3,mid2=r-(r-l)/3;
if(g(mid1)<g(mid2)) r=mid2;
else l=mid1;
}
return g(l);
}
int main() {
cin>>T;
while(T--) {
cin>>n;
for(int i=1; i<=n; i++) scanf("%d%d%d",&a[i],&b[i],&d[i]);
printf("%.4lf\n",f());
}
return 0;
}P1886 【模板】单调队列 / 滑动窗口
#include<bits/stdc++.h>
using namespace std;
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int nm=1e6+10;
int n,m,ans,cnt,k;
int a[nm],pos[nm],head=1,tail;
int main(){
st();
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
while(a[i]<a[pos[tail]]&&tail>=head) tail--;
pos[++tail]=i;
if(pos[head]<=i-k) head++;
if(i>=k) cout<<a[pos[head]]<<' ';
}
head=1,tail=0;
cout<<'\n';
for(int i=1;i<=n;i++){
while(a[i]>a[pos[tail]]&&tail>=head) tail--;
pos[++tail]=i;
if(pos[head]<=i-k) head++;
if(i>=k) cout<<a[pos[head]]<<' ';
}
return 0;
}P3811 【模板】模意义下的乘法逆元
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int nm=3e6+10;
int n,p;
int inv[nm];
signed main(){
cin>>n>>p;
inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;
for(int i=1;i<=n;i++) cout<<inv[i]<<"\n";
return "MOD",0;
}P4549 【模板】裴蜀定理
#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int n,ans,k;
signed main(){
st();
cin>>n;
for(int i=1;i<=n;i++){
cin>>k;
if(i==1) ans=abs(k);
else ans=__gcd(ans,abs(k));
}
cout<<ans;
return 0;
}P5788 【模板】单调栈
#include<bits/stdc++.h>
using namespace std;
const int nm=10000005;
int n,m,top;
int a[nm],b[nm],ans[nm],pos[nm];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
b[++top]=a[1];
pos[top]=1;
for(int i=2;i<=n;i++){
while(a[i]>b[top]&&top){
ans[pos[top]]=i;
top--;
}
b[++top]=a[i];
pos[top]=i;
}
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
return 0;
}P3366 【模板】最小生成树
1.prim
#include<bits/stdc++.h>
using namespace std;
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int nm=5005;
int n,m,ans,cnt,u,v,w;
int dis[nm],val[nm][nm],vis[nm];
signed main(){
st();
cin>>n>>m;
for(int i=1;i<=n;i++) dis[i]=INT_MAX;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) val[i][j]=INT_MAX;
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
val[u][v]=val[v][u]=min(val[u][v],w);
}
dis[1]=0;
for(int j=1;j<=n;j++){
u=0;
for(int i=1;i<=n;i++) if(!vis[i]&&(u==0||dis[i]<dis[u])) u=i;
vis[u]=1;
if(dis[u]==INT_MAX){
cout<<"orz";
return 0;
}
ans+=dis[u];
for(int i=1;i<=n;i++) dis[i]=min(dis[i],val[i][u]);
}
cout<<ans;
return 0;
}
2.堆优化prim
#include<bits/stdc++.h>
using namespace std;
int n,m,ans,head[400005],to[400005],nxt[400005],val[400005],vis[400005];
int cnt;
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> > q;
void add(int u,int v,int w){
cnt++;
to[cnt]=v;
val[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
}
void tree(int x){
q.push(P(0,1));
while(n&&q.size()){
int x=q.top().second,va=q.top().first;
q.pop();
if(vis[x]==1) continue;
vis[x]=1;
ans+=va;
n--;
for(int i=head[x];i;i=nxt[i]){
int v=to[i];
if(vis[v]==1) continue;
q.push(P(val[i],v));
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,val;
cin>>x>>y>>val;
add(x,y,val);
add(y,x,val);
}
tree(1);
if(n!=0) cout<<"orz";
else cout<<ans;
return 0;
}3.kruskal
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[200005],ans;
int gen(int x){
if(fa[x]==x) return x;
return fa[x]=gen(fa[x]);
}
bool bing(int x,int y){
int fx=gen(x),fy=gen(y);
if(fx==fy) return 0;
fa[fx]=fy;
return 1;
}
struct tree{
int val,x,y;
}t[200005];
bool cmp(tree a,tree b){
return a.val<b.val;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++) cin>>t[i].x>>t[i].y>>t[i].val;
sort(t+1,t+m+1,cmp);
for(int i=1;i<=m;i++){
if(bing(t[i].x,t[i].y)){
n--;
ans+=t[i].val;
//cout<<t[i].x<<' '<<t[i].y<<endl;
}
if(n==1){
cout<<ans;
return 0;
}
}
cout<<"orz";
return 0;
}P3367 【模板】并查集
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[200005];
int gen(int x){
if(fa[x]==x) return x;
return fa[x]=gen(fa[x]);
}
void bing(int x,int y){
int fx=gen(x);
int fy=gen(y);
if(fx==fy) return;
fa[fx]=fy;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
int z,x,y;
cin>>z>>x>>y;
if(z==1) bing(x,y);
else{
int fx=gen(x);
int fy=gen(y);
if(fx==fy) cout<<"Y\n";
else cout<<"N\n";
}
}
return 0;
}P3371 【模板】单源最短路径（弱化版）
1.SPFA（Bellman–Ford的优化版本）
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,s,val[500004],dis[500004];
int vis[500004],head[500004],to[500004],nxt[500004];
void add(int u,int v,int w){
cnt++;
val[cnt]=w;
to[cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
typedef pair<int,int> p;
priority_queue<p,vector<p>,greater<p> > q;
void spfa(int s){
dis[s]=0;
q.push(p(0,s));
while(!q.empty()){
int u=q.top().second;
q.pop();
vis[u]=0;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(dis[v]>val[i]+dis[u]){
dis[v]=val[i]+dis[u];
if(!vis[v]){
vis[v]=1;
q.push(p(dis[v],v));
}
}
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
for(int i=0;i<=500003;i++) dis[i]=INT_MAX;
spfa(s);
for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
return 0;
} 2.Dijkstra
#include<bits/stdc++.h>
using namespace std;
int n,m,s,cnt,dis[500005];
int head[500005],val[500005],to[500005],nxt[500005],vis[500005];
typedef pair<int,int> P;
priority_queue<P,vector<P>,greater<P> > q;
void add(int u,int v,int w){
cnt++;
to[cnt]=v;
val[cnt]=w;
nxt[cnt]=head[u];
head[u]=cnt;
}
void f(int x){
dis[x]=0;
q.push(P(0,x));
while(q.size()){
int u=q.top().second,w=q.top().first;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=nxt[i]){
int v=to[i];
if(val[i]+w>=dis[v]) continue;
dis[v]=val[i]+w;
q.push(P(dis[v],v));
}
}
}
int main(){
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
for(int i=0;i<=500004;i++) dis[i]=INT_MAX;
f(s);
for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
return 0;
}3.Floyd 详见 B3647 【模板】Floyd
4.Johnson 详见 P5905 【模板】全源最短路（Johnson）
| 5.区别 | 最短路算法 | Floyd | Bellman–Ford（SPFA） | Dijkstra | Johnson |
|---|---|---|---|---|---|
| 最短路类型 | 全源最短路 | 单源最短路 | 单源最短路 | 全源最短路 | |
| 作用于 | 任意图 | 任意图 | 非负权图 | 任意图 | |
| 能否检测负环 | 能 | 能 | 不能 | 能 | |
| 时间复杂度 |
P3378 【模板】堆
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int n,p,x;
int main(){
cin>>n;
while(n--){
cin>>p;
if(p==1){
cin>>x;
q.push(x);
}
else if(p==2) cout<<q.top()<<"\n";
else q.pop();
}
return 0;
} P3379 【模板】最近公共祖先（LCA）
#include<bits/stdc++.h>
using namespace std;
const int nm=1e6+5;
int n,m,s,cnt,x,y,k;
int to[nm],head[nm],nxt[nm],d[nm],f[nm][30];
void add(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
void dfs(int u,int fa){
d[u]=d[fa]+1;
f[u][0]=fa;
for(int i=head[u];i;i=nxt[i]) if(!d[to[i]]) dfs(to[i],u);
}
int lca(int x,int y){
if(d[x]<d[y]) swap(x,y);
for(int i=k;i>=0;i--){
if(d[f[x][i]]>=d[y]) x=f[x][i];
if(d[x]==d[y]) break;
}
if(x==y) return x;
for(int i=k;i>=0;i--){
if(f[x][i]!=f[y][i]){
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>s;
k=log2(n)+1;
for(int i=1;i<=n-1;i++){
cin>>x>>y;
add(x,y);
add(y,x);
}
f[s][0]=s;
dfs(s,0);
for(int i=1;i<=k;i++) for(int j=1;j<=n;j++) f[j][i]=f[f[j][i-1]][i-1];
for(int i=1;i<=m;i++){
cin>>x>>y;
cout<<lca(x,y)<<"\n";
}
return 0;
} P3385 【模板】负环
#include<bits/stdc++.h>
using namespace std;
int T,n,m,cnt,s,val[3005],dis[3005],tot[3005];
int vis[3005],head[3005],to[3005],nxt[3005];
queue<int> q;
void add(int u,int v,int w) {
cnt++;
val[cnt]=w;
to[cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
bool bfs() {
dis[1]=0;
q.push(1);
vis[1]=1;
while(q.size()) {
int u=q.front();
q.pop();
vis[u]=0;
for(int i=head[u]; i; i=nxt[i]) {
int v=to[i];
if(val[i]+dis[u]>=dis[v]) continue;
dis[v]=val[i]+dis[u];
tot[v]=tot[u]+1;
if(vis[v]==0) q.push(v);
if(tot[v]>=n) return 0;
}
}
return 1;
}
signed main() {
cin>>T;
while(T--) {
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(to,0,sizeof(to));
memset(nxt,0,sizeof(nxt));
memset(val,0,sizeof(val));
memset(head,0,sizeof(head));
memset(tot,0,sizeof(tot));
cin>>n>>m;
for(int i=1; i<=m; i++) {
int u,v,w;
cin>>u>>v>>w;
add(u,v,w);
if(w>=0) add(v,u,w);
}
if(bfs()) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}B3611 【模板】传递闭包
#include<bits/stdc++.h>
using namespace std;
int n,m,k,ans;
int dis[205][205];
int main(){
cin>>n;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>dis[i][j];
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) dis[i][j]|=dis[i][k]&&dis[k][j];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) cout<<dis[i][j]<<' ';
cout<<"\n";
}
return 0;
}B3644 【模板】拓扑排序 / 家谱树
#include<bits/stdc++.h>
using namespace std;
int n,m=1,cnt;
int val[10005],to[10005],nxt[10005],head[105],du[105];
void add(int id,int nx){
cnt++;
to[cnt]=nx;
nxt[cnt]=head[id];
head[id]=cnt;
}
queue<int> q;
void tops(){
for(int i=1;i<=n;i++) if(du[i]==0) q.push(i);
while(q.size()){
int x=q.front();
cout<<x<<' ';
q.pop();
for(int i=head[x];i;i=nxt[i]){
int v=to[i];
du[v]--;
if(du[v]==0) q.push(v);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
while(m){
add(i,m);
du[m]++;
cin>>m;
}
}
tops();
return 0;
} B3647 【模板】Floyd
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int nm=105;
int n,m,k,cnt,ans,u,v,w;
int val[nm][nm],f[nm][nm];
int main(){
st();
cin>>n>>m;
memset(val,0x3f,sizeof(val));
for(int i=1;i<=m;i++){
cin>>u>>v>>w;
val[u][v]=val[v][u]=min(val[u][v],w);
}
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j) f[i][j]=val[i][j];
for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) cout<<f[i][j]<<' ';
cout<<'\n';
}
return 0;
}P3865 【模板】ST 表 & RMQ 问题
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100005],f[100005][25],l,r;
void g(int x,int y){
int k=log2(n);
for(int j=1;j<=k;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
return;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
f[i][0]=a[i];
}
g(1,n);
for(int i=1;i<=m;i++){
cin>>l>>r;
int k=log2(r-l+1);
cout<<max(f[l][k],f[r-(1<<k)+1][k])<<"\n";
}
return 0;
}B4324 【模板】双向链表
#include<bits/stdc++.h>
using namespace std;
#define int long long
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int nm=1e6+10;
int n,m,k,ans,op,x,y;
int nxt[nm],lst[nm],val[nm],vis[nm];
signed main(){
st();
cin>>n>>m;
for(int i=1;i<=n;i++){
if(i<n) nxt[i]=i+1;
lst[i]=i-1;
}
nxt[0]=1;
while(m--){
cin>>op>>x;
if(vis[x]) continue;
nxt[lst[x]]=nxt[x];
lst[nxt[x]]=lst[x];
if(op==1){
cin>>y;
if(x!=y){
lst[x]=lst[y];
nxt[x]=y;
nxt[lst[y]]=x;
lst[y]=x;
}
}
else if(op==2){
cin>>y;
if(x!=y){
lst[x]=y;
nxt[x]=nxt[y];
lst[nxt[y]]=x;
nxt[y]=x;
}
}
else{
vis[x]=1;
n--;
}
}
if(n==0) cout<<"Empty!";
else for(int i=nxt[0];i;i=nxt[i]) cout<<i<<' ';
return 0;
}P4779 【模板】单源最短路径（标准版）
详见 P3371 【模板】单源最短路径（弱化版）
P8306 【模板】字典树
#include<bits/stdc++.h>
using namespace std;
#define ll long long
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int nm=3e6+10;
int t,n,cnt=1,q;
int a[nm][70],sum[nm];
string s;
int getnum(int id){
if(s[id]-'a'>=0&&s[id]-'a'<26) return s[id]-'a';
if(s[id]-'A'>=0&&s[id]-'A'<26) return s[id]-'A'+26;
return s[id]-'0'+52;
}
void add(){
int now=1;
for(int i=0;i<s.length();i++){
int num=getnum(i);
if(!a[now][num]) a[now][num]=++cnt;
now=a[now][num];
sum[now]++;
}
}
int query(){
int now=1;
for(int i=0;i<s.length();i++){
int num=getnum(i);
if(!a[now][num]) return 0;
now=a[now][num];
}
return sum[now];
}
void solve(){
for(int i=1;i<=cnt;i++){
sum[i]=0;
for(int j=0;j<=61;j++) a[i][j]=0;
}
cnt=1;
cin>>n>>q;
while(n--){
cin>>s;
add();
}
while(q--){
cin>>s;
cout<<query()<<'\n';
}
}
signed main(){
st();
cin>>t;
while(t--) solve();
return 0;
}
P11615 【模板】哈希表
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
namespace fastIO
{
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}
inline void read(string&s){char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}
inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}
inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
inline void write(const string&s){for(register int i=0;i<(int)s.size();i++){putchar(s[i]);}}
inline void write(const char&c){putchar(c);}
}using namespace fastIO;
const int MAXN=1e7+7;
const int mod=18556744073709551616;
int base=13;
const int m=5e6;
int n;
int a[MAXN];
int vis[MAXN];
int b[MAXN];
int sum;
inline void Hash(int k,int v)
{
int pos=k%MAXN;
while(vis[pos]&&b[pos]!=k)
{
pos=(pos+1)%MAXN;
}
b[pos]=k;
a[pos]=v;
vis[pos]=1;
}
inline int find(int k)
{
int pos=k%MAXN;
while(vis[pos])
{
if(b[pos]==k)
{
return a[pos];
}
pos=(pos+1)%MAXN;
}
return 0;
}
signed main()
{
cin>>n;
int ans=0;
for(int i=1;i<=n;i++)
{
int x,y;
read(x);
read(y);
int ans=find(x);
Hash(x,y);
sum+=i*ans;
}
write(sum);
return 0;
}\color{#52C41A}{普及+/提高}
P2197 【模板】Nim 游戏
#include<bits/stdc++.h>
using namespace std;
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int t,n,k,ans;
int main(){
st();
cin>>t;
while(t--){
cin>>n;
ans=0;
for(int i=1;i<=n;i++){
cin>>k;
ans^=k;
}
if(ans) cout<<"Yes\n";
else cout<<"No\n";
}
return 0;
}P2613 【模板】有理数取余
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nm=1e5+10;
int n,m,p=19260817;
string s1,s2;
int qp(int a,int b){
int ans=1;
while(b){
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans;
}
signed main(){
cin>>s1>>s2;
for(int i=0;i<s1.length();i++) n=(n*10+s1[i]-'0')%p;
for(int i=0;i<s2.length();i++) m=(m*10+s2[i]-'0')%p;
cout<<n*qp(m,p-2)%p;
return 0;
}
P3368 【模板】树状数组 2
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],k,l,r,mm,b[500005];
int lowbit(int x){
return x&(-x);
}
void update(int pos,int val){
while(pos<=n){
a[pos]+=val;
pos+=lowbit(pos);
}
}
int query(int pos){
int sum=0;
while(pos>0){
sum+=a[pos];
pos-=lowbit(pos);
}
return sum;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>b[i];
update(i,b[i]-b[i-1]);
}
for(int i=1;i<=m;i++){
cin>>k>>l;
if(k==1){
cin>>r>>mm;
update(l,mm);
update(r+1,-mm);
}
else cout<<query(l)<<endl;
}
return 0;
}P3372 【模板】线段树 1
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int nm=1e6+10;
int n,m,x,y,k,ans,cnt,op;
int a[nm],lazy[nm],sum[nm],l[nm],r[nm];
void pushup(int id){
sum[id]=sum[id<<1]+sum[id<<1|1];
}
void biuld(int id,int l,int r){
if(l==r){
sum[id]=a[l];
return;
}
int mid=(l+r)>>1;
biuld(id<<1,l,mid);
biuld(id<<1|1,mid+1,r);
pushup(id);
}
void pushdown(int id,int l,int r){
int mid=(l+r)>>1;
lazy[id<<1]+=lazy[id];
lazy[id<<1|1]+=lazy[id];
sum[id<<1]+=(mid-l+1)*lazy[id];
sum[id<<1|1]+=(r-mid)*lazy[id];
lazy[id]=0;
}
void update(int id,int tl,int tr,int l,int r,int val){
if(tl>=l&&tr<=r){
sum[id]+=val*(tr-tl+1);
lazy[id]+=val;
return;
}
int mid=(tl+tr)>>1;
if(lazy[id]) pushdown(id,tl,tr);
if(l<=mid) update(id<<1,tl,mid,l,r,val);
if(r>mid) update(id<<1|1,mid+1,tr,l,r,val);
pushup(id);
}
int query(int id,int tl,int tr,int l,int r){
if(tl>=l&&tr<=r) return sum[id];
int mid=(tl+tr)>>1,ans=0;
if(lazy[id]) pushdown(id,tl,tr);
if(l<=mid) ans+=query(id<<1,tl,mid,l,r);
if(r>mid) ans+=query(id<<1|1,mid+1,tr,l,r);
return ans;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
biuld(1,1,n);
while(m--){
cin>>op>>x>>y;
if(op==1){
cin>>k;
update(1,1,n,x,y,k);
}
else cout<<query(1,1,n,x,y)<<"\n";
}
return 0;
}P3373 【模板】线段树 2
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,mod;
const int MAXN = 1e5+5;
int a[MAXN];
int sum[MAXN<<2],lazy[MAXN<<2],mul[MAXN<<2]; void pushup(int id){
sum[id]=(sum[id<<1]+sum[id<<1|1])%mod;
}
void pushdown(int id,int l,int r){
int mid=(l+r)>>1;
sum[id<<1]=(sum[id<<1]*mul[id])%mod;
lazy[id<<1]=(lazy[id<<1]*mul[id])%mod;
mul[id<<1]=(mul[id<<1]*mul[id])%mod;
sum[id<<1|1] =(sum[id<<1|1] *mul[id])%mod;
lazy[id<<1|1]=(lazy[id<<1|1]*mul[id])%mod;
mul[id<<1|1] =(mul[id<<1|1] *mul[id])%mod;
mul[id] = 1;
sum[id<<1]=(sum[id<<1]+((mid-l+1)*lazy[id])%mod)%mod;
lazy[id<<1] = (lazy[id<<1]+lazy[id]) % mod;
sum[id<<1|1] = (sum[id<<1|1]+((r - mid)*lazy[id])%mod)% mod;
lazy[id<<1|1] = (lazy[id<<1|1]+lazy[id] ) % mod;
lazy[id]=0;
}
void build(int id,int l,int r){
mul[id]=1;
if(l==r){
sum[id]=a[l]%mod;
return;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
pushup(id);
}
void update(int id,int tl,int tr,int l,int r,int val){
if(l<=tl&&r>=tr){
sum[id]+=(tr-tl+1)*val;
sum[id]%=mod;
lazy[id]+=val;
lazy[id]%=mod;
return;
}
pushdown(id,tl,tr);
int mid=(tl+tr)>>1;
if(l<=mid) update(id<<1,tl,mid,l,r,val);
if(r>mid) update(id<<1|1,mid+1,tr,l,r,val);
pushup(id);
}
void update2(int id,int tl,int tr,int l,int r,int val){
if(l<=tl&&r>=tr){
sum[id]*=val;
sum[id]%=mod;
mul[id]*=val;
mul[id]%=mod;
lazy[id]*=val;
lazy[id]%=mod;
return;
}
pushdown(id,tl,tr);
int mid=(tl+tr)>>1;
if(l<=mid) update2(id<<1,tl,mid,l,r,val);
if(r>mid) update2(id<<1|1,mid+1,tr,l,r,val);
pushup(id);
}
int query(int id,int tl,int tr,int l,int r){
int ans=0;
if(l<=tl&&r>=tr){
return sum[id];
}
pushdown(id,tl,tr);
int mid=(tl+tr)>>1;
if(l<=mid) ans=(ans+query(id<<1,tl,mid,l,r))%mod;
if(r>mid) ans=(ans+query(id<<1|1,mid+1,tr,l,r))%mod;
return ans;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>mod;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(m--){
int p;
cin>>p;
if(p==1){
int x,y,k;
cin>>x>>y>>k;
update2(1,1,n,x,y,k);
} else if(p==2){
int x,y,k;
cin>>x>>y>>k;
update(1,1,n,x,y,k);
}
else{
int x,y;
cin>>x>>y;
cout<<query(1,1,n,x,y)%mod<<"\n";
}
}
return 0;
}
//屎P3374 【模板】树状数组 1
#include<bits/stdc++.h>
using namespace std;
int n,m,a[500005],k,l,r;
int lowbit(int x){
return x&(-x);
}
void add(int x,int y){
while(x<=n){
a[x]+=y;
x+=lowbit(x);
}
}
int q(int r){
int ans=0;
while(r>0){
ans+=a[r];
r-=lowbit(r);
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>k;
add(i,k);
}
for(int i=1;i<=m;i++){
cin>>k>>l>>r;
if(k==1) add(l,r);
else cout<<q(r)-q(l-1)<<endl;
}
return 0;
} P3375 【模板】KMP
#include<bits/stdc++.h>
using namespace std;
void st(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int nm=1e6+10;
int n,m,k,ans,cnt;
int nxt[nm];
string s,t;
int main(){
st();
cin>>s>>t;
s=" "+s,t=" "+t;
int slen=s.length(),tlen=t.length();
int j=0;
for(int i=2;i<tlen;i++){
while(j&&t[j+1]!=t[i]) j=nxt[j];
if(t[j+1]==t[i]) nxt[i]=++j;
}
j=0;
for(int i=1;i<slen;i++){
while(j&&t[j+1]!=s[i]) j=nxt[j];
if(t[j+1]==s[i]) j++;
if(j==tlen-1){
cout<<i-tlen+2<<'\n';
j=nxt[j];
}
}
for(int i=1;i<tlen;i++) cout<<nxt[i]<<' ';
return 0;
}