牛客多校第三场A，C+权值线段树

待补：H，J

A题
知识点：dfs序，LCA性质

题意：给定两颗树a和b，每棵树n个节点，每个节点都有自己的权重。规定n个节点中有k个关键节点（k至少为2至多为n），能否忽略某一个a树和b树中相同编号的关键节点，使得两树剩余关键节点的lca满足：在a树中lca的权值要大于在b数中lca的权值。如果可行，请输出可行方案的方案数。

思路：
性质1：一棵树中若干节点的lca就是这若干个点中dfs序最小和最大节点的lca。

这样就好做了。我们对于两颗树分别写lca，对于k个关键节点分别忽略枚举做出答案即可

PS：第一次写封装的代码，两棵树lca属实毒瘤，不知道性质更是没法做这个题，ex捏，而且枚举的点最多可以到n个，很有可能就卡倍增lca了，只能树剖lca+lca性质+dfs序去搞了。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
    
    int nex,to;
};
const int N=5e5+10;
int key[N],a[N],b[N],keyy[100005];
struct tree
{
    
node edge[N<<1],edge2[N<<1];
int dep[N],head[N],tot,fa[N],top[N],son[N],siz[N],dfsorder[N],cnt,dfn[N];
void add(int from,int to)
{
    
    edge[++tot].nex=head[from];
    edge[tot].to=to;
    head[from]=tot;
}
void DFS1(int now,int fath)
{
    
    if(key[now]) dfsorder[++cnt]=now,dfn[now]=cnt;
    fa[now]=fath;
    siz[now]=1;son[now]=0;
    dep[now]=dep[fath]+1;
    for(int i=head[now];i;i=edge[i].nex){
    
        if(edge[i].to==fath)
            continue;
        DFS1(edge[i].to,now);
        siz[now]+=siz[edge[i].to];
        if(siz[son[now]]<siz[edge[i].to])
            son[now]=edge[i].to;
    }
}
void DFS2(int now,int topx)//topx，先重儿子再轻儿子
{
    
    top[now]=topx;
    if(son[now])
    {
    
        DFS2(son[now],topx);
    }
    else
        return ;
    for(int i=head[now];i;i=edge[i].nex)
    {
    
        if(edge[i].to!=fa[now]&&edge[i].to!=son[now])
        {
    
            DFS2(edge[i].to,edge[i].to);
        }
    }
}

int LCA(int x,int y)
{
    
    while(top[x]!=top[y])
    {
    
        if(dep[top[x]]<dep[top[y]])
        {
    
            swap(x,y);
        }
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

}t1,t2;

int main()
{
    
    int n,k;
    cin>>n>>k;
    for(int i=1,temp;i<=k;i++)
    {
    
        cin>>temp;key[temp]=i;keyy[i]=temp;
    }
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=2,p;i<=n;i++)
    {
    
        cin>>p;t1.add(i,p);t1.add(p,i);
    }
    for(int i=1;i<=n;i++)
        cin>>b[i];
    for(int i=2,p;i<=n;i++)
    {
    
        cin>>p;t2.add(i,p);t2.add(p,i);
    }
    t1.DFS1(1,0);t1.DFS2(1,1);//t1.DFS3(1,0);
    t2.DFS1(1,0);t2.DFS2(1,1);//t2.DFS3(1,0);
    ll la,lb,ans=0;
    for(int i=1;i<=k;i++){
    
        if(t1.dfn[keyy[i]]==1) la=t1.LCA(t1.dfsorder[2],t1.dfsorder[k]);
        else if(t1.dfn[keyy[i]]==k) la=t1.LCA(t1.dfsorder[1],t1.dfsorder[k-1]);
        else la=t1.LCA(t1.dfsorder[1],t1.dfsorder[k]);
        if(t2.dfn[keyy[i]]==1) lb=t2.LCA(t2.dfsorder[2],t2.dfsorder[k]);
        else if(t2.dfn[keyy[i]]==k) lb=t2.LCA(t2.dfsorder[1],t2.dfsorder[k-1]);
        else lb=t2.LCA(t2.dfsorder[1],t2.dfsorder[k]);
        if(a[la]>b[lb]) ans++;
    }
    printf("%lld\n",ans);
	return 0;
}

C
字符串排序。

虽然说是字符串排序，但是方案有好几种。

最危险的一种：卡线过，不过只能怪自己

#include <iostream>
#include <algorithm>
const int N = 2e6+100;
std::string s[N];
bool cmp(const std::string &a,const std::string &b)
{
    
    std::string s1=a+b;
    std::string s2=b+a;
    return s1<s2;
}
int main()
{
    
    std::cin.tie(0);
    std::cout.tie(0);
    std::ios::sync_with_stdio(0);
    int n;
    std::cin>>n;
    for(int i=1;i<=n;i++)
    {
    
        std::cin>>s[i];
    }
    std::sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
    
        std::cout<<s[i];
    }
    //cout<<endl;

    return 0;
}

另外一种：虽然暴力，但是我有剪枝

这种代码应该算是正解了，跑了1秒多点，不到时间限制的1/3

#include<bits/stdc++.h>
using namespace std;
char ch[20000005];
string a[2000005];
int cnt,nl,ml;
bool cmp(string &n,string &m)
{
    
	int minn=min(n.length()-1,m.length()-1);
	if(n.length()==m.length())
        return n<m;
    for(int i=0;i<=minn;i++)
		if(n[i]!=m[i])
            return n[i]<m[i];
    return n+m<m+n;
}
int main()
{
    
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	    cin>>a[i];
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)
	    cout<<a[i];
	return 0;
}

权值线段树。
要开线段树分裂了，但是我发现自己的权值线段树忘干净了捏。所以搞一下。

前置知识：基础线段树（非常熟练），离散化（掌握操作）。

主要用处：主要用于记录某一个区间出现的次数，例如给定一个数组，我们按照顺序插入，我们就能够得到这个数组中某个区间里某个元素出现的次数。
实例：第树查询区间第K大的值，第k小的值，某个数在一个区间里出现了多少次等

#include <iostream>
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)/2)
using namespace std;

const int N = 1e5+100;

int tree[N<<2],tag[N<<2];

int query_max(int p,int l,int r,int k)
{
    
    if(k<=0)
        return 0;
    if(l==r)
        return l;
    int right=tree[rs];
    if(k<=right)
        return query_max(rs,mid+1,r,k);
    else
        return query_max(ls,l,mid,k-right);
}
int query_min(int p,int l,int r,int k)
{
    
    if(k<=0)
        return 0;
    if(l==r){
    
        return l;
    }
    int left=tree[ls];
    if(k<=left)
        return query_min(ls,l,mid,k-left);
    else
        return query_min(rs,mid+1,r,k);
}
int query_num(int l,int r,int p,int x)
{
    
    if(l==r)
        return tree[p];
    else{
    
        if(x<=mid)
            return query_num(l,mid,ls,x);
        else
            return query_num(mid+1,r,rs,x);
    }
}
void fix(int l,int r,int p,int x)
{
    
    if(l==r){
    
        tree[p]++;
        return ;
    }
    if(x<=mid)
        fix(l,mid,ls,x);
    if(x>mid)
        fix(mid+1,r,rs,x);
    tree[p]=tree[ls]+tree[rs];
}