徐州网络赛
B. so easy
离散然后并查集，赛后发现暴力也能过。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair < int , int > P;
const int N = 2e6 + 10;
const int inf = 0x3f3f3f3f;
struct node{
int x,y;
}a[N];
int b[N],c[N],tot,q,n,fa[N];
int get(int x)
{
if(x==fa[x]) return x;
return fa[x]=get(fa[x]);
}
int main ()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&a[i].x,&a[i].y);
c[i]=a[i].y;
}
sort(c+1,c+q+1);
int m=unique(c+1,c+q+1)-c-1;
b[++tot]=c[1];
for(int i=2;i<=m;i++)
{
if(c[i]-c[i-1]>1){
b[++tot]=c[i-1]+1;
}
b[++tot]=c[i];
}
if(c[m]+1<=n) b[++tot]=c[m]+1;
for(int i=1;i<=tot;i++)
fa[i]=i;
for(int i=1;i<=q;i++)
{
a[i].y=lower_bound(b+1,b+tot+1,a[i].y)-b;
if(a[i].x==1){
int u=get(a[i].y);
fa[u]=u+1;
}
else{
printf("%d\n",b[get(a[i].y)]);
}
}
return 0;
}D. Carneginon
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > P;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
ull f[N],p[N];
ull f1[N];
char s[N],str[N];
int q;
void Hash()
{
int len=strlen(s+1);
p[0]=1;
for(int i=1;i<=len;i++)
{
f[i]=f[i-1]*131+(s[i]-'a'+1);
p[i]=p[i-1]*131;
}
}
void hash1()
{
int len=strlen(str+1);
for(int i=1;i<=len;i++)
{
f1[i]=f1[i-1]*131+(str[i]-'a'+1);
}
}
ull get(int l,int r)
{
return f[r]-f[l-1]*p[r-l+1];
}
ull get1(int l,int r)
{
return f1[r]-f1[l-1]*p[r-l+1];
}
int main ()
{
int len,len1;
scanf("%s",s+1);
len1=strlen(s+1);
Hash();
scanf("%d",&q);
while(q--)
{
scanf("%s",str+1);
len=strlen(str+1);
if(len==len1){
bool f=true;
for(int i=1;i<=len;i++){
if(s[i]!=str[i]) {
f=false;
break;
}
}
puts(f?"jntm!":"friend!");
}
else if(len<len1){
hash1();
bool f=false;
for(int i=1;i+len-1<=len1;i++){
if(get(i,i+len-1)==get1(1,len)){
f=true;
break;
}
}
puts(f?"my child!":"oh, child!");
}
else{
hash1();
bool f=false;
for(int i=1;i+len1-1<=len;i++){
if(get(1,len1)==get1(i,i+len1-1)){
f=true;
break;
}
}
puts(f?"my teacher!":"senior!");
}
}
return 0;
}E. XKC's basketball team
倒序遍历，维护一个值递增的数组，同时保存下标，因为如果a[i]比a[i+1]小，这个a[i]是无用的，所以维护一个值递增，下标递减的数组，每次二分即可，这样二分到的值一定是位置最大的
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
const int maxn = 1e6 + 5;
int w[maxn];
int st[maxn];
int ed[maxn],ans[maxn];
int main()
{
int n, m;
scanf("%d%d",&n, &m);
for(int i = 1; i <= n; i++)
scanf("%d",&w[i]);
st[1] = w[n];
ed[1] = n;
int ss= 1;
ans[n]=-1;
for(int i = n-1; i >= 1; i--)
{
if(w[i] > st[ss])
{
st[++ss] = w[i];
ed[ss] = i;
}
int p=lower_bound (st+1,st+ss+1,w[i]+m)-st;
if(p>ss) ans[i]=-1;
else ans[i]= ed[p]-i-1;
}
for(int i=1;i<=n;i++){
printf("%d",ans[i]);
if(i!=n) putchar(' ');
}
puts("");
return 0;
}G. Colorful String
这题真是气死我了，马拉车板子抄错了，T成sb了，啊啊啊啊。
首先马拉车找到以当前位置为中心的回文串左端点，由于不能暴力算，所以我们可以计算每个字符对答案的贡献，ai记录距离i最近的j字符的位置，那么这个位置到以当前字符为中心的回文串最左端点贡献都是1，预处理一下即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair < int , int > P;
const int N = 6e5 + 10;
const int inf = 0x3f3f3f3f;
char s[N], tmp[N];
int p[N];
int aa[N], a[N][30];
void manacher() {
int len = strlen(s + 1);
int tot = 0;
tmp[tot++] = '$';
tmp[tot++] = '#';
for (int i = 1; i <= len; i++) {
tmp[tot++] = s[i];
tmp[tot++] = '#';
}
len = tot;
int mx = 0, id = 0;
for (int i = 1; i < len; i++)
{
p[i] = mx > i ? min(mx - i, p[2 * id - i]) : 1;
while (tmp[i + p[i]] == tmp[i - p[i]]) p[i] ++;
if (i + p[i] > mx) {
mx = p[i]+i;
id = i;
}
}
int st = 1;
ll ans = 0;
for (int i = 2; i < len-1; i++)
{
int L = i/2-p[i]/2 + 1;
for (int j = 0; j < 26; j++)
{
if (a[st][j] >= L)
{
ans += a[st][j] - L + 1;
}
}
if (tmp[i] == '#') st++;
}
printf("%lld\n", ans);
}
int main() {
scanf("%s", s + 1);
int len = strlen(s + 1);
for (int i = 0; i < 26; i++)
aa[i] = -1;
for (int i = 1; i <= len; i++) {
aa[s[i] - 'a'] = i;
for (int j = 0; j < 26; j++)
a[i][j] = aa[j];
}
manacher();
return 0;
}M. Longest subsequence
$a[i][j]$预处理$i$后面大于等于$j$字符最近的位置。
基于这样的一种贪心过程，选取$x$个字符与$t$串的前$x$字符相同，然后再选取一个字符大于$t$串的第$x+1$个字符，所以要贪心寻找的最近位置,还有就是最后要有个地方要注意，如果两个串前几个字符相同，退出时还要计算一次
得第几啊！
我们学校100名左右(╯°A°)╯︵○○○
那也可以了