题意：
给定n个字符串S1,S2,S3,...,Sn，把它们排序
设排序结果为Sp1,Sp2,Sp3,...,Spn
现在给定q个任务，每个任务的格式都是"要求在排序结果中Sa恰好在Sb前一个"
你排出的串满足第i个任务，就可以得到2^i(2的i次方)的奖励
现在有两个问题:
1.求相邻两项LCP平方和W的最大值
2.求出当W最大时能获得最多奖励的排序结果
数据&部分分：
对于 10%的数据，n ≤ 10，q = 1， 每个字符串的长度不超过 50；
对于 20%的数据，n ≤ 50，q = 1， 每个字符串的长度不超过 50；
对于 50%的数据，n ≤ 1000，q ≤ 1000， 每个字符串的长度不超过 1000；
对于 70%的数据，任意字符串不为其他任何一个字符串的前缀；
对于100%的数据， n ≤ 40 000， q ≤ 100 000， 每个字符串的长度不超过10 000；
对于 100%的数据，所有字符串的长度和不超过 200000。
bzoj坑爹啊，没有数据范围，还好Codevs上有
思路：
嗯，WJMZBMR远古巨神的神题，肯定不是我等一般人能做出来的
当然，在我有理有据的乱搞之前，我们先要确定这道题考的是啥
多个串，很像AC自动机，但LCP又跟AC自动机联系不起来，
苦苦思索2晚上无果后我的思路到了关键的一点：陈立杰在2012年的《后缀自动机讲稿》上有这么一句话
然后我就确定了：不会有后缀数据结构，毕竟CTSC也不太可能会出后缀数组
好，那么字符串还剩下什么数据结构呢
我们看数据范围的最后一条
答案脱口而出：Trie树！
对，就是Trie树大暴力
整理一下思路：我们明确两个大方向
（1）根据历史的进程，这道题一定是Trie树
（2）Trie树上的LCP，其实就是LCA的深度
好，现在我们开始做题
我们写一个动态Trie动态维护排序信息
别急，先打打暴力，看看有没有什么特殊性质
于是我在数学课上手算了4组数据发现
第一问是tm逗你玩的，W最大的情况是"字典序"
本来想着dp的我抱头痛哭
严谨证明的话...不太会
可能是在Trie树上搞个路径统计？
可以知道的是：一个字符串排列就相当于Trie树上一条从根出发回到根的路径
不知道，反正这一问在Trie树上按字典序dfs一下就好了
我们看第二问
第二问会发现，越往后奖励越多，所以我们考虑操作离线倒序，如果当前任务可以取就取到，然后更改Trie树上的路径(我就是在这yy出了LinkCutTrie的)
于是开始了漫长的手推
草稿纸都用了一张多，最后发现可以弄一个Trie链剖分+树套树
看了看前人的代码长度大概都是这么做的吧
然后在纸上写了很多乱七八糟的东西
...要滚去写作业了，幸运的是找到了曾经的题解
也算是看了一点点吧
毕竟还是个没学上的蒟蒻不可能一下子A掉CTSC的是不是？
放个链接吧
https://wenku.baidu.com/view/d6e7e02b647d27284b73516a.html?from=search
#include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #define ll long long using namespace std; const int maxn=40010; const int maxq=100010; int n,q,dfn; int x[maxq],y[maxq]; char SS[maxn]; struct Trie { Trie *ch[27]; int Size,dep,rnk; Trie *prev,*next; Trie *first,*last; Trie *father,*top; Trie() { memset(ch,0,sizeof(ch)); Size=0; father=0; prev=next=first=last=0; } Trie *pre() { Trie *now; for(now=this;now->prev;now=now->prev); return now; } Trie *suf() { Trie *now; for(now=this;now->next;now=now->next); return now; } Trie *insert(int val) { Trie* &now=ch[val]; if (now==0) { now=new Trie; now->father=this; Size++; } return now; } int count() { Trie *now=pre(); int cnt=0; while(now) { ++cnt; now=now->next; } return cnt; } bool find(Trie*o) { Trie *now=pre(); while(now) { if(now==o)return true; now=now->next; } return false; } bool canFirst(Trie*c) { if (c==first)return true; if (first != 0 || c->prev != 0)return false; if (c->suf()==last && c->count()!=Size)return false; return true; } bool canLast(Trie*c) { if (c == last)return true; if (last!=0 || c->next!=0)return false; if (c->pre()==first && c->count()!=Size)return false; return true; } bool canNext(Trie*c1,Trie*c2) { if (c1->next==c2)return true; if (c1->next!=0 || c2->prev!=0)return false; if (c1==last || c2==first)return false; if (c1->find(c2))return false; if (c1->pre()==first && c2->suf()==last && c1->count()+c2->count()<Size)return false; return true; } void dfs(int de) { rnk=dfn++; dep=de; if(father==0) top=0; else if(father->Size>1)top=father; else top=father->top; for(int i=0;i<27;i++)if(ch[i]!=0)ch[i]->dfs(dep+1); } }; int todolis[maxq]; Trie *es[maxn],*ed[maxn],*rt; Trie *getLCA(Trie *a, Trie *b) { while("woxihuan_keduoli") { if(a==b)return a; if(a==rt || b==rt)return rt; if( (a->top->dep) < (b->top->dep) )swap(a,b); a=a->top; } } void set(Trie *a,Trie *b) { Trie *l=getLCA(a,b); while(a->top!=l) { Trie*fa=a->top; fa->last=a; a=fa; } while(b->top!=l) { Trie*fa=b->top; fa->first=b; b=fa; } a->next=b,b->prev=a; } bool check(Trie *a, Trie *b) { Trie *l=getLCA(a, b); while(a->top!=l) { Trie*fa=a->top; if(!fa->canLast(a))return false; a=fa; } while(b->top!=l) { Trie*fa=b->top; if(!fa->canFirst(b))return false; b=fa; } if(!l->canNext(a,b))return false; return true; } bool cmp(Trie*a, Trie*b){return (a->rnk) < (b->rnk);} ll ans,cnt; int main() { scanf("%d%d",&n,&q); rt=new Trie; for(int i=0;i<n;i++) { scanf("%s",SS); int len=strlen(SS); Trie *temp=rt; for(int j=0;j<len;j++)temp=temp->insert(SS[j]-'a'+1); temp=temp->insert(0); ed[i]=temp; } ll ans=0; rt->dfs(0); for(int i=0;i<q;i++) scanf("%d%d",&x[i],&y[i]),--x[i],--y[i]; for(int i=q-1;i>=0;i--) if(check(ed[x[i]],ed[y[i]])) { set(ed[x[i]],ed[y[i]]);++cnt;todolis[i]=1; } for(int i=0;i<n;i++)es[i]=ed[i]; sort(es,es+n,cmp); ll tmp; for(int i=0;i<n-1;i++) { tmp=getLCA(es[i],es[i+1])->dep; ans+=tmp*tmp; } printf("%lld %lld ",ans,cnt); for(int i=0;i<q;i++)if(todolis[i])printf("%d ",i+1); return 0; }
OI加油 期末加油