#include<bits/stdc++.h> #define N 100005 usingnamespacestd; typedeflonglong ll;
template<typename T> inlinevoidread(T &nnum){ T x = 0, f = 1; char cch = getchar(); for (; cch > '9' || cch < '0'; cch = getchar()) if (cch == '-') f = -1; for (; cch <= '9' && cch >= '0'; cch = getchar()) x = (x << 3) + (x << 1) + (cch ^ '0'); nnum = x * f; }
int n, st[N], ed[N], bst[N], bed[N], g[N<<2], len[N<<2], m, L, Q, sz, bcnt; char s[N<<2], t[N<<2]; bool vis[N<<2]; int ch[N<<2][26], tot, in[N], rnk[N<<2], pre[N<<2], nxt[N<<2], num[N<<2], top; ll ans1[N], ans2[N], v[N], cnt[N<<2], nowans, a, b, c; pair<int, pair<int, int> > changed[N<<2];
voidinsert(int l, int r){ //建Trie树 int x = 0; for (int i = l; i <= r; i++) { if (!ch[x][s[i]-'a']) { ch[x][s[i]-'a'] = ++tot; } x = ch[x][s[i]-'a']; len[x] = i - l + 1; } }
inline ll calc(ll x){ if (x <= 0) return0; elsereturn x * (x + 1) / 2; }
inline ll V(int x){ if (!cnt[x]) return0; return1ll * b * cnt[x] + 1ll * a * len[x]; }
voiddel(int l, int r, int id){ //删除操作,修改点权+修改链表+修改答案 int x = 0; for (int i = l; i <= r; i++) { x = ch[x][s[i]-'a']; cnt[x] -= v[id]; if (V(x) < c && vis[x]) { //若当前节点不满足条件且现在在集合G里 if (!(--num[g[len[x]]])) { //将g[len_S]的出现次数-1 int y = g[len[x]], _pre = pre[y], _nxt = nxt[y]; nowans -= calc(y - _pre - 1) + calc(_nxt - y - 1); nowans += calc(_nxt - _pre - 1); //修改当前答案 changed[++top] = make_pair(_pre, make_pair(pre[_pre], nxt[_pre])); changed[++top] = make_pair(_nxt, make_pair(pre[_nxt], nxt[_nxt])); //记录一下哪些链表元素被修改了 回滚时暴力修改回去 nxt[_pre] = _nxt; pre[_nxt] = _pre; } vis[x] = 0; } } }
voidadd(int l, int r, int id){ //增加操作,仅修改点权,不修改链表和答案 int x = 0; for (int i = l; i <= r; i++) { x = ch[x][s[i]-'a']; cnt[x] += v[id]; if (V(x) >= c && !vis[x]) { //若当前节点已满足条件且不在集合G里 num[g[len[x]]]++; vis[x] = 1; } } }
structnode{ int l, r, id; booloperator < (const node bb) const { return in[l] != in[bb.l] ? l < bb.l : r > bb.r; //由于是只删不增的回滚莫队 所以右端点从大到小排序 } } q[N];
intmain(){ read(n); read(a); read(b); read(c); sz = sqrt(n); bcnt = 1; for (int i = 1; i <= n; i++) { if (i % sz == 1) bst[bcnt] = i; in[i] = bcnt; if (i % sz == 0) bed[bcnt] = i, bcnt++; //表示一个块的起始和结束位置 } if (n % sz == 0) bcnt--; bed[bcnt] = n; for (int i = 1; i <= n; i++) { read(v[i]); } for (int i = 1, l; i <= n; i++) { scanf("%s", t + 1); l = strlen(t + 1); L = max(L, l); st[i] = m + 1; for (int j = 1; j <= l; j++) { s[++m] = t[j]; } ed[i] = m; } for (int i = 1; i <= L; i++) { read(g[i]); } read(Q); for (int i = 1; i <= Q; i++) { read(q[i].l); read(q[i].r); q[i].id = i; } sort(q + 1, q + Q + 1); for (int i = 1; i <= n; i++) { insert(st[i], ed[i]); } num[L+1] = 114514; //哼哼啊啊啊啊 int now = 1, nl = 0, nr = 0; for (int i = 1; i <= bcnt; i++) { nowans = 0; for (int j = bst[i]; j <= n; j++) { add(st[j], ed[j], j); //将 当前块的起始位置 ~ N 的所有字符串加入集合P } int lst = 0; for (int j = 1; j <= L + 1; j++) { if (num[j]) { //预处理出初始链表和初始答案 pre[j] = lst; nxt[lst] = j; nowans += calc(j - lst - 1); lst = j; } } nr = n; //当前右端点从N开始向左移动 while (in[q[now].l] == i) { while (nr > q[now].r) del(st[nr], ed[nr], nr), nr--; top = 0; //右端点的修改不用回滚! ll tmp = nowans; //记录当前答案 方便查询完这次之后直接改回去 nl = bst[i]; while (nl < q[now].l) del(st[nl], ed[nl], nl), nl++; //删除时 点权,链表,答案可以一起修改 但是撤销时最好要一个一个撤销比较好写 ans1[q[now].id] = nowans; ans2[q[now].id] = 1ll * L * (L+1) / 2; for (int j = q[now].l - 1; j >= bst[i]; j--) add(st[j], ed[j], j); //撤销对Trie树上点权的修改 while (top) { //撤销对链表的修改 pre[changed[top].first] = changed[top].second.first; nxt[changed[top].first] = changed[top].second.second; top--; } nowans = tmp; //撤销对答案的修改 now++; } while (nr >= bst[i]) { //把剩余字符串全部删掉 相当于让P集合回到空集 del(st[nr], ed[nr], nr); nr--; } } for (int i = 1; i <= Q; i++) { ans1[i] = ans2[i] - ans1[i]; if (ans1[i] == 0) puts("0/1"); elseif (ans1[i] == ans2[i]) puts("1/1"); else { ll gcd = __gcd(ans1[i], ans2[i]); ans1[i] /= gcd; ans2[i] /= gcd; printf("%lld/%lld\n", ans1[i], ans2[i]); } } return0; }