A. Captain, run
I didn't expect to do this at all. I've been thinking about sorting and how to do it. In the middle, I typed a strange line segment tree because of an error in understanding. I found that the error has passed for 2h. I really didn't have the idea to run directly, and then basically zero..... WTCL
Because \ (A {P _i} < = B {P _i} \) will explode, the B of the crystal destroyed after must be less than the minimum value of A destroyed before
Let \ (f[i][j] \) mean that the minimum value of the first \ (I \) crystals \ (a[i] \) is the maximum number of crystals that j can destroy
If you don't destroy the current crystal \ (f[i][j]=f[i-1][j] \)
Destroy the current crystal \ (f[i][min(j,a[i])]=max(f[i-1][j])+1 \)
This transfer is obviously \ (O(N^2) \), so consider how to optimize it
Let's expand the discussion by \ (min \)
Originally, DP can be written as
for (int j = 1; j <= tot; ++j)
f[i][j] = f[i - 1][j];
if (a[i].b > a[i].a)
for (int j = a[i].b + 1; j <= tot; ++j)
f[i][a[i].a] = max(f[i][a[i].a], f[i - 1][j] + 1);
else
{
for (int j = a[i].b + 1; j < a[i].a; ++j)
f[i][j] = f[i - 1][j] + 1;
for (int j = a[i].a; j <= tot; ++j)
f[i][a[i].a] = max(f[i][a[i].a], f[i - 1][j] + 1);
}
Then, we need to use OIER's favorite segment tree. The inheritance operation is to do nothing. Taking \ (max \) is the interval maximum value, updating is a single point of modification, and there is an interval addition. Just use the segment tree board directly
Due to the operation of the boss of \ (Eafoo \), the Hornet is a little strange
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100005;
struct node
{
int a, b;
} a[maxn];
int ls[maxn << 1 | 1], tot;
void lsh(int n)
{
tot = n << 1;
for (int i = 1; i <= n; ++i)
ls[(i << 1) - 1] = a[i].a, ls[i << 1] = a[i].b;
sort(ls + 1, ls + tot + 1);
tot = unique(ls + 1, ls + tot + 1) - ls - 1;
for (int i = 1; i <= n; ++i)
{
a[i].a = upper_bound(ls + 1, ls + tot + 1, a[i].a) - ls - 1;
a[i].b = upper_bound(ls + 1, ls + tot + 1, a[i].b) - ls - 1;
}
}
int tree[maxn << 3], lazy[maxn << 3];
void push_down(int x, int l, int r)
{
int mid = (l + r) >> 1;
tree[x << 1] += lazy[x];
tree[x << 1 | 1] += lazy[x];
lazy[x << 1] += lazy[x];
lazy[x << 1 | 1] += lazy[x];
lazy[x] = 0;
}
void add(int x, int l, int r, int L, int R)
{
if (L <= l && r <= R)
{
++lazy[x];
++tree[x];
return;
}
if (lazy[x])
push_down(x, l, r);
int mid = (l + r) >> 1;
if (L <= mid)
add(x << 1, l, mid, L, R);
if (R > mid)
add(x << 1 | 1, mid + 1, r, L, R);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
int ask(int x, int l, int r, int L, int R)
{
if (L <= l && r <= R)
return tree[x];
if (tree[x])
push_down(x, l, r);
int mid = (l + r) >> 1;
int ans = -1;
if (L <= mid)
ans = ask(x << 1, l, mid, L, R);
if (R > mid)
ans = max(ans, ask(x << 1 | 1, mid + 1, r, L, R));
return ans;
}
void update(int x, int l, int r, int d, int ne)
{
if (l == r)
{
tree[x] = max(tree[x], ne);
return;
}
if (tree[x])
push_down(x, l, r);
int mid = (l + r) >> 1;
if (d <= mid)
update(x << 1, l, mid, d, ne);
if (d > mid)
update(x << 1 | 1, mid + 1, r, d, ne);
tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%d%d", &a[i].a, &a[i].b);
lsh(n);
for (int i = 1; i <= n; ++i)
{
if (a[i].b >= a[i].a)
{
int k = ask(1, 1, tot, a[i].b + 1, tot) + 1;
update(1, 1, tot, a[i].a, k);
}
else
{
int k = ask(1, 1, tot, a[i].a, tot) + 1;
update(1, 1, tot, a[i].a, k);
add(1, 1, tot, a[i].b, a[i].a - 1);
}
}
printf("%d\n", tree[1]);
return 0;
}
B. Shadow devil
Another problem I can't solve is really too weak
The color is considered separately. The color contributes to the subtree where it is located. The contribution of multiple colors in the subtree is calculated only once. Using the idea of difference on the tree, maintain the chain and (another new term?), In the dfs order, the corresponding node is + 1 and - 1 at the lca of the adjacent nodes of the same color, so as to ensure that the contribution is only 1. In order to obtain the number of adjacent nodes in the dfs order, use set for maintenance (set is ordered).
Then when all colors are finished, the problem becomes to find the sum of subtree weights. Because there is still depth, the chairman tree is used, and the dfs corresponding to each depth is ordered into a new version
Find the corresponding subtree in the corresponding version...
Because I'm too good to write anything. If you don't understand, please read other big guys' blogs
The code completely imitates the writing method of fengwu senior (because I don't know the chairman tree yet)
After learning the chairman tree, see if there is anything that needs to be corrected. Dig a pit
#include <cstring>
#include <cstdio>
#include<algorithm>
#include<set>
using namespace std;
const int maxd=100005;
struct edge{
int net,to;
}e[maxd<<1|1];
int head[maxd],tot;
int n,m;
void add(int u,int v){
e[++tot].net=head[u];
head[u]=tot;
e[tot].to=v;
}
struct node{
int col,dep,dfsl,dfsr,id;
bool operator < ( node x)const{
return x.dfsl>dfsl;
}
}d[maxd];
set<node>st[maxd];
bool cmp(node x,node y){
if(x.dep!=y.dep)return x.dep<y.dep;
return x.dfsl<y.dfsl;
}
int cnt,max_dep[maxd],dep[maxd],dfsl[maxd],dfsr[maxd];
int fa[maxd][25];
int root[maxd];
void dfs(int x){
d[x].dfsl=++cnt;
max_dep[x]=d[x].dep;
for(int i=head[x];i;i=e[i].net){
int v=e[i].to;
d[v].dep=d[x].dep+1;
fa[v][0]=x;
for(int i=1;i<=20;++i)fa[v][i]=fa[fa[v][i-1]][i-1];
dfs(v);
max_dep[x]=max(max_dep[x],max_dep[v]);
}
d[x].dfsr=cnt;
}
int LCA(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=20;i>=0;--i)if(dep[fa[x][i]]>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=20;i>=0;--i)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
struct president_tree{
int left_son[maxd*80],right_son[maxd*80];
int siz[maxd*80];
int tmp;
void pushup(int x){
siz[x]=0;
if(left_son[x])siz[x]+=siz[left_son[x]];
if(right_son[x])siz[x]+=siz[right_son[x]];
return;
}
void insert(int pre,int &x,int l,int r,int pos,int v){
if(!x){x=++tmp;siz[x]=siz[pre];left_son[x]=left_son[pre];right_son[x]=right_son[pre];}
if(l==r){siz[x]+=v;return;}
int mid=(l+r)>>1;
if(pos<=mid){
if(left_son[x]==left_son[pre])left_son[x]=0;
insert(left_son[pre],left_son[x],l,mid,pos,v);
}else{
if(right_son[x]==right_son[pre])right_son[x]=0;
insert(right_son[pre],right_son[x],mid+1,r,pos,v);
}
pushup(x);return;
}
int query(int x,int l,int r,int L,int R){
if(!x)return 0;
if(L<=l&&r<=R)return siz[x];
int mid=(l+r)>>1,ans=0;
if(L<=mid)ans+=query(left_son[x],l,mid,L,R);
if(R>mid)ans+=query(right_son[x],mid+1,r,L,R);
return ans;
}
}tree;
int main(){
//freopen(,r,stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&d[i].col),d[i].id=i;
for(int i=2;i<=n;++i){int x;scanf("%d",&x);add(x,i);}
d[1].dep=1;dfs(1);
for(int i=1;i<=n;++i){
dep[i]=d[i].dep;
dfsl[i]=d[i].dfsl;
dfsr[i]=d[i].dfsr;
}
sort(d+1,d+n+1,cmp);
for(int i=1;i<=n;++i){
tree.insert(root[d[i].dep-1],root[d[i].dep],1,n,d[i].dfsl,1);
st[d[i].col].insert(d[i]);
int lca;
node nu;nu.id=0;
node pre=st[d[i].col].find(d[i])==st[d[i].col].begin()?nu:*--st[d[i].col].find(d[i]);
node nxt=((++st[d[i].col].find(d[i]))==st[d[i].col].end())?nu:*++st[d[i].col].find(d[i]);
if(pre.id){
lca=LCA(d[i].id,pre.id);
tree.insert(root[d[i].dep-1],root[d[i].dep],1,n,dfsl[lca],-1);
}
if(nxt.id){
lca=LCA(d[i].id,nxt.id);
tree.insert(root[d[i].dep-1],root[d[i].dep],1,n,dfsl[lca],-1);
}
if(pre.id&&nxt.id){
lca=LCA(pre.id,nxt.id);
tree.insert(root[d[i].dep-1],root[d[i].dep],1,n,dfsl[lca],1);
}
}
for(int i=1;i<=m;++i){
int u,d;scanf("%d%d",&u,&d);
printf("%d\n",tree.query(root[min(dep[u]+d,max_dep[u])],1,n,dfsl[u],dfsr[u]));
}
return 0;
}
C. Flip a coin
The most important question in the exam, but he put it in T3
Let \ (f[i][j] \) represent how many subsequences with essentially different length of j start with the i-th character after the i-th character
It can be found that if there are multiple identical letters after i, because the sequence starting with the same letter can be obtained in front, then the number of essentially different letters is the scheme number of the first letter
\(f[i][j]=\sum_{k=1}^{26} f[pos[i][k]][j-1]\)
Preprocess the position where the first letter appears backward (excluding itself) a-z in each position
Then memorize the search
#include <cstring>
#include <cstdio>
using namespace std;
const int mod=998244353;
char c[3015];
int n;
int rem[3005][3005];
int flag[27],re[3005][27];
bool vis[3005][3005];
int ask(int x,int l){
if(vis[x][l])return rem[x][l];
vis[x][l]=1;
if(n-x+1==l)return rem[x][l]=1;
if(n-x+1<l)return rem[x][l]=0;
long long ans=0;
for(int i=0;i<=27;++i)
if(re[x][i])ans+=ask(re[x][i],l-1);
return rem[x][l]=(ans%mod);
}
int main(){
scanf("%s",c+1);
n=strlen(c+1);
int l;scanf("%d",&l);
for(int i=n;i>=1;--i){
for(int j=1;j<=26;++j)re[i][j]=flag[j];
rem[i][1]=1;vis[i][1]=1;
flag[c[i]-'a'+1]=i;
}
long long ans=0;
for(int i=1;i<=n;++i)int k=ask(i,l);
for(int i=1;i<=26;++i){
int k=flag[i];
ans=(ans+rem[flag[i]][l])%mod;
}
printf("%lld\n",ans);
return 0;
}