codeforces 666E. Forensic Examination（广义后缀自动机，Parent树，线段树合并）

传送门：
解题思路：

很坑的一道题，需要离线处理，假如只有一组询问，那么就可以直接将endpos集合直接累加输出就好了。
这里就要将询问挂在树节点上，在进行线段树合并时查询就好了。
代码超级容易写挂的。
注意要将匹配串时尽量找到最浅根，易于统计答案。
倍增处理就好了。
代码：

  1 #include<cstdio>
  2 #include<vector>
  3 #include<cstring>
  4 #include<algorithm>
  5 const int N=1000000;
  6 struct int_2{
  7     int vl;
  8     int ps;
  9 }imt;
 10 struct sant{
 11     int tranc[26];
 12     int len;
 13     int pre;
 14 }s[N];
 15 struct pnt{
 16     int hd;
 17     int fa[24];
 18     int rt;
 19     std::vector<int>posquery;
 20 }p[N];
 21 struct ent{
 22     int twd;
 23     int lst;
 24 }e[N];
 25 struct trnt{
 26     int ls;
 27     int rs;
 28     int_2 val;
 29 }tr[N<<2];
 30 struct qnt{
 31     int l;
 32     int r;
 33     int pl;
 34     int pr;
 35     int lt;
 36     int pos;
 37     int_2 ans;
 38     void Insert(void)
 39     {
 40         scanf("%d%d%d%d",&l,&r,&pl,&pr);
 41         lt=pr-pl+1;
 42         return ;
 43     }
 44 }q[N];
 45 char tmp[N];
 46 char str[N];
 47 std::vector<int>lpnt[N];
 48 int n,m,Q;
 49 int siz;
 50 int fin;
 51 int cnt;
 52 int tnt;
 53 void ade(int f,int t)
 54 {
 55     cnt++;
 56     e[cnt].twd=t;
 57     e[cnt].lst=p[f].hd;
 58     p[f].hd=cnt;
 59     return ;
 60 }
 61 int_2 max(int_2 x,int_2 y)
 62 {
 63     if(x.vl!=y.vl)
 64         return x.vl>y.vl?x:y;
 65     return x.ps<y.ps?x:y;
 66 }
 67 void pushup(int spc)
 68 {
 69     tr[spc].val=max(tr[tr[spc].ls].val,tr[tr[spc].rs].val);
 70     return ;
 71 }
 72 void update(int l,int r,int &spc,int pos)
 73 {
 74     if(!spc)
 75         spc=++tnt;
 76     if(l==r)
 77     {
 78         tr[spc].val.vl++;
 79         tr[spc].val.ps=pos;
 80         return ;
 81     }
 82     int mid=(l+r)>>1;
 83     if(pos<=mid)
 84         update(l,mid,tr[spc].ls,pos);
 85     else
 86         update(mid+1,r,tr[spc].rs,pos);
 87     pushup(spc);
 88     return ;
 89 }
 90 void merge(int &spc1,int spc2)
 91 {
 92     if(!spc1||!spc2)
 93     {
 94         spc1|=spc2;
 95         return ;
 96     }
 97     if(!tr[spc1].ls&&!tr[spc1].rs)
 98     {
 99         tr[spc1].val.vl+=tr[spc2].val.vl;
100         return ;
101     }
102     merge(tr[spc1].ls,tr[spc2].ls);
103     merge(tr[spc1].rs,tr[spc2].rs);
104     pushup(spc1);
105     return ;
106 }
107 int_2 query(int l,int r,int ll,int rr,int spc)
108 {
109     if(!spc||l>rr||ll>r)
110         return imt;
111     if(ll<=l&&r<=rr)
112         return tr[spc].val;
113     int mid=(l+r)>>1;
114     return max(query(l,mid,ll,rr,tr[spc].ls),query(mid+1,r,ll,rr,tr[spc].rs));
115 }
116 void Insert(int c)
117 {
118     int nwp,nwq,lsp,lsq;
119     nwp=++siz;
120     s[nwp].len=s[fin].len+1;
121     for(lsp=fin;lsp&&!s[lsp].tranc[c];lsp=s[lsp].pre)
122         s[lsp].tranc[c]=nwp;
123     if(!lsp)
124         s[nwp].pre=1;
125     else{
126         lsq=s[lsp].tranc[c];
127         if(s[lsq].len==s[lsp].len+1)
128             s[nwp].pre=lsq;
129         else{
130             nwq=++siz;
131             s[nwq]=s[lsq];
132             s[nwq].len=s[lsp].len+1;
133             s[nwp].pre=s[lsq].pre=nwq;
134             while(s[lsp].tranc[c]==lsq)
135             {
136                 s[lsp].tranc[c]=nwq;
137                 lsp=s[lsp].pre;
138             }
139         }
140     }
141     fin=nwp;
142     return ;
143 }
144 void Dfs(int x)
145 {
146     for(int i=p[x].hd;i;i=e[i].lst)
147     {
148         int to=e[i].twd;
149         Dfs(to);
150         merge(p[x].rt,p[to].rt);
151     }
152     for(int i=0;i<p[x].posquery.size();i++)
153     {
154         int h=p[x].posquery[i];
155         q[h].ans=query(1,m,q[h].l,q[h].r,p[x].rt);
156     }
157     return ;
158 }
159 int main()
160 {
161     scanf("%s",str+1);
162     n=strlen(str+1);
163     scanf("%d",&m);
164     siz=1;
165     for(int i=1;i<=m;i++)
166     {
167         fin=1;
168         scanf("%s",tmp+1);
169         int tml=strlen(tmp+1);
170         for(int j=1;j<=tml;j++)
171         {
172             Insert(tmp[j]-'a');
173             update(1,m,p[fin].rt,i);
174         }
175     }
176     for(int i=2;i<=siz;i++)
177         ade(s[i].pre,i);
178     for(int i=1;i<=siz;i++)
179     {
180         p[i].fa[0]=s[i].pre;
181     }
182     for(int j=1;j<=23;j++){
183         for(int i=1;i<=siz;i++)
184         {
185             p[i].fa[j]=p[p[i].fa[j-1]].fa[j-1];
186             
187         }
188     }
189     scanf("%d",&Q);
190     for(int i=1;i<=Q;i++)
191     {
192         q[i].Insert();
193         lpnt[q[i].pr].push_back(i);
194     }
195     int root=1;
196     int lth=0;
197     for(int i=1;i<=n;i++)
198     {
199         int c=str[i]-'a';
200         while(root&&!s[root].tranc[c])
201         {
202             root=s[root].pre;
203             lth=s[root].len;
204         }
205         if(!root)
206         {
207             root=1;
208             lth=0;
209             continue;
210         }
211         root=s[root].tranc[c];
212         lth++;
213         for(int j=0;j<lpnt[i].size();j++)
214         {
215             int h=lpnt[i][j];
216             int o=root;
217             if(lth<q[h].lt)
218                 continue;
219             for(int k=23;k>=0;k--)
220             {
221                 int nxt=p[o].fa[k];
222                 if(s[nxt].len>=q[h].lt)
223                     o=nxt;
224             }
225             p[o].posquery.push_back(h);
226             q[h].pos=o;
227         }
228     }
229     Dfs(1);
230     for(int i=1;i<=Q;i++)
231     {
232         if(q[i].ans.vl==0)
233             q[i].ans.ps=q[i].l;
234         printf("%d %d
",q[i].ans.ps,q[i].ans.vl);
235     }
236     return 0;
237 }