1
namespace FastIO{
2
 char *p1,*p2,buf[1<<14];
3
 #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,(1<<14),stdin),p1==p2)?EOF:*p1++)
4
 template <typename T>
5
 inline void read(T& x){
6
     x=0;
7
     register int t=1;
8
     register char ch=getchar();
9
     while(ch<'0'||ch>'9'){
10
         if(ch=='-')t=-1;
11
         ch=getchar();
12
     }
13
     while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
14
     x*=t;
15
 }
16
 template <typename T>
17
 void write(T x){
18
     if(x<0)putchar('-'),x=-x;
19
     if(x>9)write(x/10);
20
     putchar(x%10^48);
21
 }
22
 template <typename T>
23
 inline void writeln(T x,char sep='\n'){
24
  write(x);putchar(sep);
25
 }
26
}
27
using namespace FastIO;

1
#include<bits/stdc++.h>
2
using namespace FastIO;
3
using namespace std;
4
const int N=1e6+10;
5
int n,T,i,j,x,y,a[N][21];
6
int Query(int x,int y){
7
    int z=__lg(y-x+1);
8
    return max(a[x][z],a[y-(1<<z)+1][z]);
9
}
10
int main(){
11
    read(n);read(T);
12
    for(i=1;i<=n;i++)read(a[i][0]);
13
    for(j=1;j<=21;j++)
14
        for(i=1;i<=n-(1<<j)+1;i++)
15
            a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);
16
 while(T--)read(x),read(y),writeln(Query(x,y));
17
}

1
#include<bits/stdc++.h>
2
#define ls x<<1
3
#define rs x<<1|1
4
using namespace std;
5
typedef long long ll;
6
const ll N=1e6+10;
7
ll n,m,mod,i,op,x,y,z,a[N];
8
struct Node{ll sum,l,r,Mul,Add;}Tree[N];
9
void Build(ll x,ll l,ll r){
10
 Tree[x].l=l,Tree[x].r=r;Tree[x].Mul=1;
11
 if(l==r){Tree[x].sum=a[l]%mod;return;}
12
 ll mid=(l+r)>>1;
13
 Build(ls,l,mid);Build(rs,mid+1,r);
14
 Tree[x].sum=(Tree[ls].sum+Tree[rs].sum)%mod;
15
}
16
void Spread(ll x){
17
    Tree[ls].sum=(Tree[x].Mul*Tree[ls].sum+((Tree[ls].r-Tree[ls].l+1)*Tree[x].Add)%mod)%mod;
18
    Tree[rs].sum=(Tree[x].Mul*Tree[rs].sum+(Tree[x].Add*(Tree[rs].r-Tree[rs].l+1))%mod)%mod;
19
    Tree[ls].Mul=(Tree[ls].Mul*Tree[x].Mul)%mod;
20
    Tree[rs].Mul=(Tree[rs].Mul*Tree[x].Mul)%mod;
21
 Tree[ls].Add=(Tree[ls].Add*Tree[x].Mul+Tree[x].Add)%mod;
22
    Tree[rs].Add=(Tree[rs].Add*Tree[x].Mul+Tree[x].Add)%mod;
23
    Tree[x].Mul=1;Tree[x].Add=0;
24
}
25
void Add(ll x,ll l,ll r,ll k){
26
 if(Tree[x].l>=l&&Tree[x].r<=r){
27
  Tree[x].Add=(Tree[x].Add+k)%mod;
28
  Tree[x].sum=(Tree[x].sum+k*(Tree[x].r-Tree[x].l+1))%mod;
29
  return;
30
 }
31
 Spread(x);
32
 Tree[x].sum=(Tree[ls].sum+Tree[rs].sum)%mod;
33
 ll mid=(Tree[x].l+Tree[x].r)>>1;
34
 if(l<=mid)Add(ls,l,r,k);
35
 if(mid<r)Add(rs,l,r,k);
36
 Tree[x].sum=(Tree[ls].sum+Tree[rs].sum)%mod;
37
}
38
void Mul(ll x,ll l,ll r,ll k){
39
 if(Tree[x].l>=l&&Tree[x].r<=r){
40
  Tree[x].Add=(Tree[x].Add*k)%mod;
41
  Tree[x].Mul=(Tree[x].Mul*k)%mod;
42
  Tree[x].sum=(Tree[x].sum*k)%mod;
43
  return;
44
 }
45
 Spread(x);
46
    Tree[x].sum=Tree[ls].sum+Tree[rs].sum;
47
 ll mid=(Tree[x].l+Tree[x].r)>>1;
48
 if(l<=mid)Mul(ls,l,r,k);
49
 if(mid<r)Mul(rs,l,r,k);
50
 Tree[x].sum=(Tree[ls].sum+Tree[rs].sum)%mod;
51
}
52
ll Query(ll x,ll l,ll r){
53
 if(Tree[x].l>=l&&Tree[x].r<=r)return Tree[x].sum;
54
 Spread(x);
55
 ll v=0,mid=(Tree[x].l+Tree[x].r)>>1;
56
 if(l<=mid)v=(v+Query(ls,l,r))%mod;
57
 if(mid<r)v=(v+Query(rs,l,r))%mod;
58
 return v;
59
}
60
int main(){
61
 cin>>n>>m>>mod;
62
 for(i=1;i<=n;i++)cin>>a[i];
63
 Build(1,1,n);
64
 for(i=1;i<=m;i++){
65
  cin>>op;
66
  if(op==1)cin>>x>>y>>z,Mul(1,x,y,z);
67
  else if(op==2)cin>>x>>y>>z,Add(1,x,y,z);
68
  else cin>>x>>y,cout<<Query(1,x,y)<<'\n';
69
    }
70
}

1
const ll mod=/*模数*/;
2
ll qpow(ll x,ll y){
3
 ll s=1;
4
 while(y){
5
  if(y&1)s=s*x%mod;
6
  y>>=1;x=x*x%mod;
7
 }
8
 return s;
9
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N=3e6+10,M=70;
4
int T,q,n,i,j,l,f[N][M],sum[N];
5
char s[N];
6
int _(char x){
7
    if(x>='A'&&x<='Z')return x-65;
8
    else if(x>='a'&&x<='z')return x-71;
9
    else return x+4;
10
}
11
void Add(char str[]){
12
    int p=0,len=strlen(str),i,c;
13
    for(i=0;i<len;i++){
14
        c=_(str[i]);
15
        if(!f[p][c])f[p][c]=++l;
16
        p=f[p][c];
17
        sum[p]++;
18
    }
19
}
20
int Query(char str[]){
21
    int p=0,len=strlen(str),i,c;
22
    for(i=0;i<len;i++){
23
        c=_(str[i]);
24
        if(!f[p][c])return 0;
25
        p=f[p][c];
26
    }
27
    return sum[p];
28
}
29
int main(){
30
    cin>>T;
31
    while(T--){
32
        for(i=0;i<=l;i++)for(j=0;j<=122;j++)f[i][j]=0;
33
        for(i=0;i<=l;i++)sum[i]=0;
34
        l=0;
35
        cin>>n>>q;
36
        for(i=1;i<=n;i++)cin>>s,Add(s);
37
        for(i=1;i<=q;i++)cin>>s,cout<<Query(s)<<'\n';
38
    }
39
}

1
int main(){
2
 cin>>n>>m;memset(f,0x3f,sizeof f);
3
 for(i=1;i<=m;i++)cin>>x>>y>>z,f[x][y]=f[y][x]=z;
4
 for(i=1;i<=n;i++)f[i][i]=0;
5
 for(k=1;k<=n;k++)
6
  for(i=1;i<=n;i++)
7
   for(j=1;j<=n;j++)
8
    if(f[i][k]+f[k][j]<f[i][j])
9
                    f[i][j]=f[i][k]+f[k][j];
10
 for(i=1;i<=n;i++,cout<<'\n')
11
  for(j=1;j<=n;j++)
12
   if(f[i][j]!=2139062143)cout<<f[i][j]<<' ';
13
   else cout<<0<<' ';
14
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
int n,T,k,x,y,i,j,f[10010];
4
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
5
int main(){
6
    cin>>n>>T;
7
    for(i=1;i<=n;i++)f[i]=i;
8
    while(T--){
9
        cin>>k>>x>>y;
10
        if(k==1)f[find(x)]=find(y);
11
        else
12
            if(find(x)==find(y))cout<<"Y\n";
13
            else cout<<"N\n";
14
    }
15
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N=1e6+10;
4
int i,j,l1,l2,f[N];
5
char a[N],b[N];
6
int main(){
7
 cin>>a+1>>b+1;l1=strlen(a+1);l2=strlen(b+1);
8
 for(i=2;i<=l2;i++){
9
  while(j&&b[i]!=b[j+1])j=f[j];
10
  if(b[j+1]==b[i])j++;
11
  f[i]=j;
12
 }
13
 j=0;
14
 for(i=1;i<=l1;i++){
15
  while(j>0&&b[j+1]!=a[i])j=f[j];
16
  if(b[j+1]==a[i])j++;
17
  if(j==l2)cout<<i-l2+1<<'\n',j=f[j];
18
 }
19
 for(i=1;i<=l2;i++)cout<<f[i]<<' ';
20
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N=1e5+10,M=5e5+10,inf=INT_MAX;
4
struct Edge{int to,nxt,val;}E[M];
5
int n,m,s,i,x,y,z,cnt,head[N],dis[N],vis[N];
6
void add(int x,int y,int z){E[++cnt]={y,head[x],z};head[x]=cnt;}
7
struct Node{
8
    int x,y;
9
    bool operator<(const Node &y)const{return y.x<x;}
10
};
11
priority_queue<Node>q;
12
void Dij(){
13
 int u,v,i;dis[s]=0;q.push({0,s});
14
 while(!q.empty()){
15
  u=q.top().y;x=q.top().x;q.pop();
16
  if(vis[u])continue;
17
  vis[u]=1;
18
  for(i=head[u];i;i=E[i].nxt){
19
   v=E[i].to;
20
   if(dis[v]>dis[u]+E[i].val){
21
    dis[v]=dis[u]+E[i].val;
22
    if(!vis[v])q.push({dis[v],v});
23
   }
24
  }
25
 }
26
}
27
int main(){
28
 cin>>n>>m>>s;
29
 for(i=1;i<=n;i++)dis[i]=inf;
30
 for(i=1;i<=m;i++)cin>>x>>y>>z,add(x,y,z);
31
 Dij();
32
 for(i=1;i<=n;i++)cout<<dis[i]<<' ';
33
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
ll n,i,x,y,a[16],m[16],f[16],mul=1,ans;
5
void exgcd(ll a,ll b,ll &x,ll &y){
6
    if(!b){x=1;y=0;return;}
7
    exgcd(b,a%b,x,y);
8
    int z=x;x=y,y=z-y*(a/b);
9
}
10
int main(){
11
    cin>>n;
12
    for(i=1;i<=n;i++)cin>>x>>a[i],m[i]=x,mul*=x;
13
    for(i=1;i<=n;i++)f[i]=mul/m[i],x=y=0,exgcd(f[i],m[i],x,y),ans+=a[i]*f[i]*(x<0?x+m[i]:x);
14
    cout<<ans%mul;
15
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const ll N=3e6+10;
5
ll n,mod,i,inv[N];
6
int main(){
7
    cin>>n>>mod;inv[1]=1;
8
    cout<<1<<'\n';
9
    for(i=2;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod,cout<<inv[i]<<'\n';
10
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
const int N=1e6+10;
4
int n,m,i,l,r,a[N],q1[N],q2[N];
5
int main(){
6
    cin>>n>>m;
7
    for(i=1;i<=n;i++)cin>>a[i];
8
 l=1;r=0;
9
    for(i=1;i<=n;i++){
10
        while(l<=r&&q1[l]+m<=i)l++;
11
        while(l<=r&&a[i]<a[q1[r]])r--;
12
        q1[++r]=i;
13
        if(i>=m)cout<<a[q1[l]]<<' ';
14
    }
15
    cout<<'\n';
16
    l=1;r=0;
17
    for(i=1;i<=n;i++){
18
        while(l<=r&&q2[l]+m<=i)l++;
19
        while(l<=r&&a[i]>a[q2[r]])r--;
20
        q2[++r]=i;
21
        if(i>=m)cout<<a[q2[l]]<<' ';
22
    }
23
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
ll a,m,b,x=1,y,i,flag;
5
char ch;
6
ll qpow(ll x,ll y){
7
 ll s=1;
8
 for(;y;y>>=1,x=x*x%m)if(y&1)s=s*x%m;
9
 return s;
10
}
11
int main(){
12
 cin>>a>>m;a%=m;y=m;
13
 for(i=2;i<=sqrt(y);i++){
14
  if(y%i)continue;
15
  x*=i-1;y/=i;
16
  while(!(y%i))x*=i,y/=i;
17
 }
18
 if(y>1)x*=y-1;
19
 while((ch=getchar())<'0'||ch>'9');
20
 while(b=b*10+ch-'0',(ch=getchar())>='0'&&ch<='9')if(b>=x)flag=1,b%=x;
21
 if(b>=x)flag=1,b%=x;
22
 if(flag)b+=x;
23
 cout<<qpow(a,b);
24
}

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
const ll N=1e6+10;
5
ll n,m,i,j,s,ans,f[N];
6
struct Edge{ll x,y,v;}E[N<<1];
7
ll find(ll x){return f[x]==x?x:f[x]=find(f[x]);}
8
bool cmp(Edge x,Edge y){return x.v<y.v;}
9
void Kruskal(){
10
 int i,fx,fy;
11
    for(i=1;i<=m;i++){
12
        fx=find(E[i].x);fy=find(E[i].y);
13
        if(fx==fy)continue;
14
        ans+=E[i].v;f[fx]=fy;s++;
15
        if(s==n-1)break;
16
    }
17
}
18
int main(){
19
    cin>>n>>m;
20
    for(i=1;i<=n;i++)f[i]=i;
21
    for(i=1;i<=m;i++)cin>>E[i].x>>E[i].y>>E[i].v;
22
    sort(E+1,E+1+m,cmp);
23
    Kruskal();
24
    if(s!=n-1)return cout<<"orz",0;
25
    cout<<ans;
26
}