269

_N

ESP
ZQCa
L.妍ab
Algorithm没有冬眠
123go

itdef

#include<iostream>
#include<algorithm>
#include<string.h>

using namespace std;

const int N = 100010;

int h[N],ph[N],hp[N],s;

void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}

void down(int u)
{
int t = u;
if (u * 2 <= s && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= s && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}

void up(int x)
{
while(x/2 && h[x/2] > h[x])
{
heap_swap(x/2,x);
x /= 2;
}
}

int main()
{
int n, m = 0;
scanf("%d", &n);
while (n -- )
{
char op[5];
int k, x;
scanf("%s", op);
if (!strcmp(op, "I"))
{
scanf("%d", &x);
s ++ ;
m ++ ;
ph[m] = s, hp[s] = m;
h[s] = x;
up(s);
}

else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
else if (!strcmp(op, "DM"))
{
heap_swap(1, s);
s -- ;
down(1);
}
else if (!strcmp(op, "D"))
{
scanf("%d", &k);
k = ph[k];
heap_swap(k, s);
s -- ;
up(k);
down(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}

return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n,m;
int a[N],s;

void down(int x)
{
int t =x;
if(x * 2 <= s && a[x * 2] < a[t])
{
t = x * 2;
}
if(x * 2 + 1 <= s && a[x * 2 + 1] < a[t])
{
t = x * 2 + 1;
}
if( x != t)
{
swap(a[x],a[t]);
down(t);
}
}

int main()
{
scanf("%d%d", &n,&m);
for (int i= 1; i <=n; i++) scanf("%d",&a[i]);
s = n;
for (int i= n/2; i; i --)
{
down(i);
}

while(m--)
{
printf("%d ",a[1]);
a[1] = a[s];
s--;
down(1);
}
return 0;
}


#include<iostream>

using namespace std;

const int N = 50010;

int n,m;
int p[N],d[N];

int find(int x)
{
if(p[x] != x)
{
int t = find(p[x]);
d[x] += d[p[x]];
p[x] = t;
}
return p[x];
}

int main()
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
{
p[i]=i;
}
int res = 0;
while(m--)
{
int t,x,y;
scanf("%d%d%d",&t,&x,&y);
if(x > n || y > n) res++;
else
{
int px = find(x),py = find(y);
if( t == 1)
{
if(px == py && (d[x]-d[y]) % 3) res++;
else if(px != py)
{
p[px]=py;
d[px] = d[y] - d[x];
}
}
else
{
if (px == py && (d[x] - d[y] -1) % 3) res++;
else if(px != py)
{
p[px]=py;
d[px] = d[y] + 1 - d[x];
}
}
}
}
printf("%d\n",res);
return 0;
}


#include<iostream>

using namespace std;

const int N = 100010;

int n,m;
int p[N],s[N];

int find(int x)
{
if(p[x]!= x) p[x] = find(p[x]);
return p[x];
}

int main()
{
scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)
{
p[i] = i;
s[i] = 1;
}

while(m--)
{
char op[5];
int a,b;
scanf("%s",op);

if(op[0] == 'C')
{
scanf("%d%d",&a,&b);
if(find(a) == find(b)) continue;
s[find(b)] += s[find(a)];
p[find(a)] = find(b);
}
else if(op[1] == '1')
{
scanf("%d%d",&a,&b);
if(find(a)==find(b)) puts("Yes");
else puts("No");
}
else if(op[1] == '2')
{
scanf("%d",&a);
printf("%d\n", s[find(a)]);
}

}
return 0;
}


#include<iostream>

using namespace std;

const int N = 100010;

int n,m;
int p[N];

int find(int x)
{
if(p[x]!= x) p[x] = find(p[x]);
return p[x];
}

int main()
{
scanf("%d%d",&n,&m);

for(int i=0;i<n;i++) p[i]=i;

while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);

if(op[0] == 'M')
{
p[find(a)] = find(b);
}
else if(op[0] == 'Q')
{
if(find(a)==find(b)) puts("Yes");
else puts("No");
}

}
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010, M = 3000000;

int n;
int son[M][2],a[N],idx;

void insert(int x)
{
int p = 0;
for(int i=30;i>=0;i--)
{
int &s = son[p][x>> i & 1];
if(!s) s = ++idx;
p = s;
}
}

int query(int x)
{
int res = 0, p = 0;
for(int i=30;i>=0;i--)
{
int s = x >> i & 1;
if(son[p][!s])
{
res += 1 << i;
p = son[p][!s];
}
else
{
p = son[p][s];
}
}
return res;
}

int main()
{
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
insert(a[i]);
}

int res = 0;
for(int i=0;i<n;i++)
{
res = max(res,query(a[i]));
}
cout<< res <<endl;
return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;

int son[N][26],cnt[N],idx;
char str[N];

void insert(char str[])
{
int p = 0;
for(int i=0;str[i];i++)
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p]++;
}

int query(char str[])
{
int p = 0;
for(int i=0;str[i];i++)
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}

int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char op[2];
scanf("%s%s", op, str);
if( op[0] == 'I') insert(str);
else if (op[0] == 'Q') printf("%d\n",query(str));
}
return 0;
}


#include<iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n,m;
char p[N],s[M];
int ne[N];

int main()
{
cin >> n >> p + 1 >> m >> s + 1;

for (int i = 2, j = 0; i <= n; i ++ )
{
while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;
}

for (int i = 1, j = 0; i <= m; i ++ )
{
while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == n)
{
printf("%d ", i - n);
j = ne[j];
}
}

return 0;
}


#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100010;

int n,m;
int q[N];

int maxquery( int A, int B){

int ans = q[A];
for(int i=A;i<= B;i++) ans = max(ans,q[i]);
return ans;
}

void update(int A, int B){
q[A]=B;
}

int main(){
while(cin>>n>>m)
{
for(int i=1;i<=n;i++) cin>>q[i];
int A,B;
char C;
cin>>A>>B;
cin>>C;
while(m--)
{
if(C=='U') update(A,B);
else if(C == 'Q')
{
if(A>B) swap(A,B);
cout<<maxquery(A,B)<<endl;
}
}
}
return 0;
}