description

點擊查看題目內容

solution

Step1
無腦建$SAM$
兩個前綴的最長公共后綴就是$parent?tree$上兩點的$lca$，定義知顯然

---

Step2
離線詢問，按右端點從小到大排序

---

Step3
每加入一個字母，就將$ta$在$parent?tree$上到根節(jié)點的路徑打上$ta$的標記
如果遇到以前打的標記，則說明該節(jié)點即為舊標記與新標記的$lca$
貪心把標記覆蓋為較大的值

---

Step4
樹狀數組統(tǒng)計
下標為左端點，每次查詢下標大于等于該詢問左端點的最大深度
向根跑的過程中每一次遇到舊標記，就在樹狀數組上更新答案，并給該節(jié)點打上新標記
但樹狀數組是用來計算前綴和的，所以有一個$n?x+1$的小轉化

---

Step5
往根節(jié)點跑的過程即是$LCT$的$access$操作

---

code

#include <cstdio> #include <vector> #include <iostream> using namespace std; #define maxn 200005 struct node {int f, val, tag;int son[2]; }tree[maxn]; struct SAM {int fa, len;int son[2]; }t[maxn]; vector < pair < int, int > > G[maxn]; int last = 1, cnt = 1, n, m; char s[maxn]; int ans[maxn], maxx[maxn], num[maxn], st[maxn];int lowbit( int x ) {return x & ( -x ); }void modify( int x, int val ) {for( int i = n - x + 1;i <= n;i += lowbit( i ) )maxx[i] = max( maxx[i], val ); }int query( int x ) {int ans = 0;for( int i = n - x + 1;i;i -= lowbit( i ) )ans = max( ans, maxx[i] );return ans; }void insert( int id, int x ) {int pre = last, now = last = ++ cnt;num[id] = cnt;t[now].len = t[pre].len + 1;while( pre && ! t[pre].son[x] ) t[pre].son[x] = now, pre = t[pre].fa;if( ! pre ) t[now].fa = 1;else {int u = t[pre].son[x];if( t[pre].len + 1 == t[u].len ) t[now].fa = u;else {int v = ++ cnt;t[v] = t[u];t[v].len = t[pre].len + 1;t[u].fa = t[now].fa = v;while( pre && t[pre].son[x] == u ) t[pre].son[x] = v, pre = t[pre].fa;}} }bool isroot( int x ) {return tree[tree[x].f].son[0] == x || tree[tree[x].f].son[1] == x; }void rotate( int x ) {int fa = tree[x].f, Gfa = tree[fa].f;int k = tree[fa].son[1] == x;if( isroot( fa ) )tree[Gfa].son[tree[Gfa].son[1] == fa] = x;tree[x].f = Gfa;if( tree[x].son[k ^ 1] )tree[tree[x].son[k ^ 1]].f = fa;tree[fa].son[k] = tree[x].son[k ^ 1];tree[x].son[k ^ 1] = fa;tree[fa].f = x; }void change( int x, int val ) {tree[x].val = tree[x].tag = val; }void pushdown( int x ) {if( ! tree[x].tag ) return;if( tree[x].son[0] ) change( tree[x].son[0], tree[x].tag );if( tree[x].son[1] ) change( tree[x].son[1], tree[x].tag );tree[x].tag = 0; }void splay( int x ) {int Top = 0, y = x;st[++ Top] = y;while( isroot( y ) ) st[++ Top] = y = tree[y].f;while( Top ) pushdown( st[Top --] );while( isroot( x ) ) {int fa = tree[x].f, Gfa = tree[fa].f;if( isroot( fa ) )( ( tree[Gfa].son[0] == fa ) ^ ( tree[fa].son[0] == x ) ) ? rotate( x ) : rotate( fa );rotate( x );} }void access( int x, int val ) {int son;for( son = 0;x;son = x, x = tree[x].f ) {splay( x );modify( tree[x].val, t[x].len );tree[x].son[1] = son;}tree[son].tag = tree[son].val = val; }int main() {scanf( "%d %d %s", &n, &m, s + 1 );for( int i = 1;i <= n;i ++ ) //樹狀數組下標必須從1開始 insert( i, s[i] - '0' );for( int i = 1, l, r;i <= m;i ++ ) {scanf( "%d %d", &l, &r );G[r].push_back( make_pair( l, i ) );}for( int i = 1;i <= cnt;i ++ ) tree[i].f = t[i].fa;for( int i = 1;i <= n;i ++ ) {access( num[i], i );for( int j = 0;j < G[i].size();j ++ )ans[G[i][j].second] = query( G[i][j].first );}for( int i = 1;i <= m;i ++ )printf( "%d\n", ans[i] );return 0; }

總結

以上是生活随笔為你收集整理的「雅礼集训 2017 Day7」事情的相似度（后缀自动机+LCT+树状数组）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。