CF547E

Benzenesir · 2023-09-30 15:04:35 · 题解

这里没有哈希的题解，所以来水一篇。

不难从题目的数据范围内找到根号的条件，一共只会出现 \sqrt{n} 种不同的权值。

那不妨离线查询，对于每一种长度 k 遍历一遍所有的字符串，分离出长度为 k 的子串， 放进桶里，然后拆询问，在每个右端点处计算答案。

分离子串不难用哈希实现，总复杂度为 n^{1.5}+q。

由于这是道 CF 题，所以卡哈希，感谢 ereoth 提供的 base ，得以通过此题。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <stack>
#include <tuple>
#include <bitset>
#define ll long long
#define ull unsigned long long
#define db double
#define fp(a,b,c) for(int a=b;a<=c;a++)
#define fd(a,b,c) for(int a=b;a>=c;a--)
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define bae 12347
#define mod 1000000007
#define eb emplace_back
#define y1 y114
#define y0 y514
#define x1 x114
#define x0 x514
#define mpr make_pair
#define met(x,t) memset(x,t,sizeof(x))
#define fir first
#define sec second
#include <numeric>
#include <stdlib.h>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>

using namespace std;

inline int rd(){
    int x = 0, f = 1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9')x = (x<<1) + (x<<3) + (ch^48),ch = getchar();
    return x * f;}
const int N=2e5+10;
int n,q;
string s[N];
vector<ll>hsh[N];
vector<int> rlen;
ll powx[N],ans[N*5];
int len[N],id[N];
struct node{
    int p,coe,id,qqq;
    node(int p=0,int coe=0,int id=0,int qqq=0):p(p),coe(coe),id(id),qqq(qqq) {}
};
vector<node> qu[450];
__gnu_pbds::gp_hash_table<ll,int> mp;
//符号 编号 哪个询问
ll split(int l,int r,int id){
    return (hsh[id][r]+mod-powx[r-l+1]*hsh[id][l-1]%mod)%mod;
}
int ppip(char c){
    return c-'a'+1;
}
void build(){
    powx[0]=1;
    fp(i,1,N-10) powx[i]=(powx[i-1]*bae)%mod;
    fp(i,1,n){
        hsh[i].resize(len[i]+2);
        fp(j,1,len[i])
            hsh[i][j]=((hsh[i][j-1]*bae)%mod+ppip(s[i][j]))%mod;
    }
}

auto uni=[](vector<int> &v){
    sort(v.begin(),v.end());
    int len=unique(v.begin(),v.end())-v.begin();
    while(v.size()^len) v.pop_back();
};

void lis(){
    fp(i,1,n)
        rlen.emplace_back(len[i]);
    uni(rlen);
    fp(i,1,n){
        int kkk=lower_bound(rlen.begin(),rlen.end(),len[i])-rlen.begin()+1;
        id[i]=kkk;
    }
}

void work(int wh){
    if(qu[wh].empty()) return ;
    int lenx=rlen[wh-1];
    mp.clear();
    sort(qu[wh].begin(),qu[wh].end(),[&](node x,node y){
        return x.p>y.p;
    });
    fp(i,1,n){
        if(qu[wh].empty()) break;
        fp(j,1,len[i]-lenx+1){
            ll kkk=split(j,j+lenx-1,i);
            mp[kkk]++;
        }
        while(!qu[wh].empty()&&qu[wh].back().p==i){
            auto [p,coe,id,qqq]=qu[wh].back();
            int kkkk=split(1,len[id],id);
            qu[wh].pop_back();
            ans[qqq]+=coe*mp[split(1,len[id],id)];
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0); 
    cin >> n >> q;
    fp(i,1,n){
        cin >> s[i];
        len[i]=s[i].length();
        s[i]=" "+s[i];
    }
    build();
    lis();
    fp(i,1,q){
        int l,r,x;
        cin >> l >> r >> x;
        qu[id[x]].emplace_back(r,1,x,i);
        if(l>1) qu[id[x]].emplace_back(l-1,-1,x,i);
    }
    ll zzz=split(1,1,1),zzzz=split(1,len[2],2);
    fp(i,1,rlen.size())
        work(i);
    fp(i,1,q) cout << ans[i] << '\n'; 
    return 0;
}