F-Paper Grading

1、先不考虑交换问题， 只考虑查询。一般公共前缀问题就往字典树上去想，那么先将所有字符串转化为字典树上的东西，那么公共前缀为k，我们先找到这个点，x，那么发现所有符合条件的都在x的子树下面，那么现在可以把整个树做一个dfs序，就可以快速的表示x的子树范围，那么x的范围设置为dfn[x] , ed[x] ,一个进入dfs序，一个退出dfs序，

2、现在我们就是要在[dfn[x] , ed[x]] 之前查找[L , R ] 的个数，现在这个求解就直接容斥一下(简单的相加减) ， [dfn[x] , r] - [dfn[x] + sz[x] - 1 , r] - ([dfn[x] , l - 1] - [dfn[x] + sz[x] - 1 , l - 1])

3、 那么我们现在就是求解[1 ， dfn[x]] 里面有多少[1 , r]

4、那么发现对于某一个dfn[x]而言，只需要比它小的dfx[y] , 对于某个r来说，只需要比它小的r'

5、我们可以先把所有的字符串的所有dfn和编号id保存一下，那么可以用二维偏序来求出结果，只要看比dfn[x]小的有多少[1 , r],经典二维偏序问题,排序加树状数组可以解决

6、再考率交换问题，它会交换两个字符串，但是在上面的问题抽像出来之后，只关注dfs序和它的标号，标号肯定是不变的，那么只需要交换标号。但是交换肯定付出代价,因为在第5步，我们插入了所有的字符串，交换的话肯定需要将交换之前的贡献删除，将交换之后的贡献插入。

7、问题出现了，那么我们这个怎么插入，直接插入的话如何保证这个交换只会对后面的查询有影响，而不对前面的查询有影响。我们发现这个是否对前后有影响是因为时间原因，查询和修改的时间关系决定的。那么我们就再引入一维，时间戳t。那么第6步的基础上加一维时间t。经典三维偏序问题。

8、现在就是要求出来，对于某个[t , dfn[x] , r] ，有多少[t' , dfn[x]' , r'] , 满足 t' <= t && dfn[x]' <= dfn[x] , r' <= r

/*
 *@author spnooyseed
 */
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
struct node {
  int t , dfn , id , val , ans , op ;
}q[N * 2] , temp[N * 2] ;
int son[N * 2][28] , dfn[N] ,  cnt , bel[N] , ed[N] ;
bool cmp(node a , node b) {
  if(a.t != b.t) return a.t < b.t ;
  if(a.dfn != b.dfn) return a.dfn < b.dfn ;
  return a.id < b.id ;
}
int lowbit(int x) {
  return x & -x ;
}
int c[N] ;
void add(int x , int k) {
  while(x < N) c[x] += k , x += lowbit(x) ;
}
int ask(int x) {
  int ans = 0 ;
  while(x) ans += c[x] , x -= lowbit(x) ;
  return ans ;
}
void insert(char s[] , int id) {
  int len = strlen(s) ;
  int p = 0 ;
  for(int i = 0 ;i < len ;i ++ ) {
    int u = s[i] - 'a' + 1 ;
    if(!son[p][u]) son[p][u] = ++ cnt ;
    p = son[p][u] ;
  }
  bel[id] = p ;
  return ;
}
void dfs(int u) {
  dfn[u] = ++ cnt ;
  for(int i = 1 ; i <= 26; i ++ )
    if(son[u][i]) dfs(son[u][i]) ;
  ed[u] = cnt ;
}
char s[N] ;
int get(int k) {
  int p = 0 ;
  for(int i = 0 , j = 1 ; s[i] && j <= k ;i ++ , j ++ ) {
    int u = s[i] - 'a' + 1 ;
    if(!son[p][u]) return -1 ;
    p = son[p][u] ;
  }
  return p ;
}
ll ans[N] ;
void cdq(int l , int r) {
  if(l >= r) return ;
  int mid = l + r >> 1 ;
  cdq(l , mid) , cdq(mid + 1 , r) ;
  int i = l , j = mid + 1 , k = 0 ;
  while(i <= mid && j <= r ) {
    if(q[i].dfn <= q[j].dfn) {
      if(q[i].op)  add(q[i].id , q[i].val) ;
      temp[++ k] = q[i ++] ;
    }
    else {
      if(!q[j].op)  ans[q[j].ans] += ask(q[j].id) * q[j].val ;
      temp[++ k] = q[j ++] ;
    }
  }
  while(i <= mid) {
    if(q[i].op)  add(q[i].id , q[i].val) ;
    temp[++ k] = q[i ++] ;
  }
  while(j <= r) {
    if(!q[j].op)  ans[q[j].ans] += ask(q[j].id) * q[j].val ;
    temp[++ k] = q[j ++] ;
  }
  for(int i = l ;i <= mid ;i ++ )  if(q[i].op)  add(q[i].id , -q[i].val) ;
  for(int i = l , j = 1 ;i <= r; i ++ , j ++ ) q[i] = temp[j] ;
  return ;
}
int f[N] ;

int main()
{
  //   freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
  //   freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
  int n , m ;
  scanf("%d%d" , &n , &m) ;
  for(int i = 1; i <= n ;i ++ ) {
    scanf("%s" , s) ;
    insert(s , i) ;
  }
  cnt = 0 ;
  dfs(0) ;
  int idx = 0 ;
   // t dfn id val ans op
  for(int i = 1; i <= n ;i ++ )
   q[++ idx] = {0 , dfn[bel[i]] , i + 1 , 1 , 0 , 1} ;
  for(int i = 1; i <= m ;i ++ ) {
    int op ;
    scanf("%d" , &op) ;
    if(op == 1) {
      int a , b ;
      scanf("%d%d" , &a , &b) ;
      q[++ idx] = {i , dfn[bel[a]] , a + 1 , -1 , i , 1} ;
      q[++ idx] = {i , dfn[bel[b]] , b + 1 , -1 , i , 1} ;
      swap(bel[a] , bel[b]) ;
      q[++ idx] = {i , dfn[bel[a]] , a + 1 , 1 , i , 1} ;
      q[++ idx] = {i , dfn[bel[b]] , b + 1 , 1 , i , 1} ;
    }else {
      f[i] = 1;
      int l , r , k ;
      scanf("%s%d%d%d" , s , &k , &l , &r) ;
      int x = get(k) ;
      q[++ idx] = {i , ed[x] , r + 1 , 1 , i , 0} ;
      q[++ idx] = {i , dfn[x] - 1 , r + 1 , -1 , i , 0} ;
      q[++ idx] = {i , ed[x] , l , - 1 , i , 0} ;
      q[++ idx] = {i , dfn[x] - 1 , l , 1 , i , 0} ;
    }
  }
  sort(q + 1 , q + idx + 1 , cmp) ;
  cdq(1 , idx) ;
  for(int i = 1; i <= m ;i ++ )
    if(f[i])
     printf("%lld\n" , ans[i]) ;
  return 0 ;
}
/*
*/
cdq分治ICPC区域赛

相关

暑期专题四 CDQ分治

【cdq分治】【模板】

【学习笔记】CDQ分治（等待填坑）

cdq分治学习笔记

标签