Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- const int MAXN = 200 * 1000 + 7;
- const ll P1 = 37, Q1 = 1000 * 1000 * 1000 + 9, P2 = 41, Q2 = 1000 * 1000 * 1000 + 7;
- const ll A = 100 * 1000 + 1, B = 1000 * 1000 * 1000 + 7;
- ll ppows1[MAXN];
- ull ppows2[MAXN];
- ll apows[MAXN];
- struct ResultHash
- {
- ll value;
- int len;
- ResultHash()
- {
- value = 0;
- len = 0;
- }
- ResultHash(char c)
- {
- value = (int)c;
- len = 1;
- }
- };
- ResultHash merge(ResultHash l, ResultHash r)
- {
- ResultHash res;
- res.len = l.len + r.len;
- res.value = (l.value * apows[r.len] + r.value) % B;
- return res;
- }
- struct SegmentTree
- {
- vector<ResultHash> tree;
- SegmentTree(int n)
- {
- tree.resize(4 * n + 7);
- }
- void build(string& s, int v, int tl, int tr)
- {
- if (tl == tr)
- {
- tree[v] = ResultHash(s[tl - 1]);
- }
- else
- {
- int tm = (tl + tr) / 2;
- build(s, 2 * v, tl, tm);
- build(s, 2 * v + 1, tm + 1, tr);
- tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
- }
- }
- ResultHash get(int v, int tl, int tr, int l, int r)
- {
- if (r < tl || l > tr) return ResultHash();
- if (tl >= l && tr <= r) return tree[v];
- int tm = (tl + tr) / 2;
- return merge(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
- }
- };
- struct Hash
- {
- ll value1;
- ull value2;
- int deg;
- Hash()
- {
- value1 = 0;
- value2 = 0;
- deg = 0;
- }
- Hash(ll _value1, ull _value2, int _deg)
- {
- value1 = _value1;
- value2 = _value2;
- deg = _deg;
- }
- };
- bool operator==(Hash x, Hash y)
- {
- if (x.deg == -1 || y.deg == -1) return false;
- if (x.deg > y.deg) swap(x, y);
- x.value1 = (x.value1 * ppows1[y.deg - x.deg]) % Q1;
- x.value2 = (x.value2 * ppows2[y.deg - x.deg]);
- return x.value1 == y.value1 && x.value2 == y.value2;
- }
- bool operator<(Hash x, Hash y)
- {
- return make_pair(x.value1, x.value2) < make_pair(y.value1, y.value2);
- }
- Hash normalize(Hash x)
- {
- x.value1 = (x.value1 * ppows1[MAXN - 1 - x.deg]) % Q1;
- x.value2 = (x.value2 * ppows2[MAXN - 1 - x.deg]);
- x.deg = MAXN - 1;
- return x;
- }
- struct HashString
- {
- vector<ll>prefHashs1;
- vector<ull> prefHashs2;
- string s;
- HashString(){}
- HashString(string& _s)
- {
- s = _s;
- prefHashs1.resize((int)s.length() + 1);
- prefHashs2.resize((int)s.length() + 1);
- int n = (int)s.length();
- for (int i = 1; i <= n; i++)
- {
- int x = s[i - 1] - 'a' + 1;
- prefHashs1[i] = (prefHashs1[i - 1] + 1LL * x * ppows1[i]) % Q1;
- prefHashs2[i] = (prefHashs2[i - 1] + 1ULL * x * ppows2[i]);
- }
- s = '$' + s;
- }
- Hash getHash(int l, int r)
- {
- if (r >= (int)s.length()) return Hash(0, 0, -1);
- return normalize(Hash((prefHashs1[r] + Q1 - prefHashs1[l - 1]) % Q1, (prefHashs2[r] - prefHashs2[l - 1]), l));
- }
- string getSubstr(int l, int r)
- {
- string res;
- for (int i = l; i <= r; i++)
- {
- res += s[i];
- }
- return res;
- }
- bool cmpSubstr(int l1, int r1, int l2, int r2)
- {
- if (s[l1] != s[l2]) return s[l1] < s[l2];
- int canGo = min(r1 - l1 + 1, r2 - l2 + 1) + 1;
- int l = 1, r = canGo;
- while (r - l > 1)
- {
- int m = (l + r) / 2;
- if (getHash(l1, l1 + m - 1) == getHash(l2, l2 + m - 1))
- {
- l = m;
- }
- else
- {
- r = m;
- }
- }
- if (r == canGo)
- {
- if (r1 - l1 < r2 - l2) return true;
- return false;
- }
- return s[l1 + l] < s[l2 + l];
- }
- };
- HashString hs, hrevs;
- ll leftPos[MAXN], rightPos[MAXN], parent[MAXN], lazy[MAXN], cnt[MAXN];
- int nextId = 1;
- map<Hash, int> pals;
- char buf[MAXN];
- int gol1[MAXN], gor1[MAXN], gol2[MAXN], gor2[MAXN];
- int perm[MAXN];
- ll sumCnt[MAXN];
- string getString()
- {
- scanf("%s", buf);
- return string(buf);
- }
- bool cmpPal(int x, int y)
- {
- return hs.cmpSubstr(leftPos[x], rightPos[x], leftPos[y], rightPos[y]);
- }
- int main()
- {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- #endif
- ppows1[0] = 1;
- ppows2[0] = 1;
- apows[0] = 1;
- for (int i = 1; i < MAXN; i++)
- {
- ppows1[i] = (ppows1[i - 1] * P1) % Q1;
- ppows2[i] = (ppows2[i - 1] * P2);
- apows[i] = (apows[i - 1] * A) % B;
- }
- int n, q;
- scanf("%d %d\n", &n, &q);
- string s = getString();
- string revs = s;
- reverse(revs.begin(), revs.end());
- hs = HashString(s);
- hrevs = HashString(revs);
- for (int i = 1; i <= n; i++)
- {
- int l = 1, r = n + 3;
- int ri = n - i + 1;
- while (r - l > 1)
- {
- int m = (l + r) / 2;
- //cerr << i << " " << ri << " " << m << endl;
- //cerr << hs.getHash(i, i + m - 1).value << " " << hrevs.getHash(ri, ri + m - 1).value << endl;
- if (hs.getHash(i, i + m - 1) == hrevs.getHash(ri, ri + m - 1))
- {
- l = m;
- }
- else
- {
- r = m;
- }
- }
- gol1[i] = i - l + 1;
- gor1[i] = i + l - 1;
- // printf("%d %d\n", gol1[i], gor1[i]);
- }
- for (int i = 1; i < n; i++)
- {
- if (s[i - 1] != s[i]) continue;
- int l = 1, r = n + 3;
- int ri = n - i;
- while (r - l > 1)
- {
- int m = (l + r) / 2;
- if (hs.getHash(i, i + m - 1) == hrevs.getHash(ri, ri + m - 1))
- {
- l = m;
- }
- else
- {
- r = m;
- }
- }
- gol2[i] = i - l + 2;
- gor2[i] = i + l - 1;
- //cerr << gol2[i] << " " << gor2[i] << endl;
- }
- for (int i = 1; i <= n; i++)
- {
- int cl = gol1[i], cr = gor1[i];
- while (true)
- {
- Hash cur = hs.getHash(cl, cr);
- if (pals.find(cur) != pals.end()) break;
- pals[cur] = nextId;
- leftPos[nextId] = cl;
- rightPos[nextId] = cr;
- nextId++;
- cl++;
- cr--;
- if (cl > cr) break;
- }
- }
- for (int i = 1; i <= n; i++)
- {
- int cl = gol2[i], cr = gor2[i];
- if (gol2[i] == 0) continue;
- while (true)
- {
- Hash cur = hs.getHash(cl, cr);
- if (pals.find(cur) != pals.end()) break;
- pals[cur] = nextId;
- leftPos[nextId] = cl;
- rightPos[nextId] = cr;
- nextId++;
- cl++;
- cr--;
- if (cl > cr) break;
- }
- }
- vector<pair<int, int> >toSortLen;
- for (int i = 1; i < nextId; i++)
- {
- toSortLen.push_back(make_pair(rightPos[i] - leftPos[i] + 1, i));
- }
- sort(toSortLen.begin(), toSortLen.end());
- for (int i = 0; i < (int)toSortLen.size(); i++)
- {
- int x = toSortLen[i].second;
- if (rightPos[x] - leftPos[x] + 1 <= 2) continue;
- parent[x] = pals[hs.getHash(leftPos[x] + 1, rightPos[x] - 1)];
- }
- for (int i = 1; i <= n; i++)
- {
- int x = pals[hs.getHash(gol1[i], gor1[i])];
- lazy[x]++;
- }
- for (int i = 1; i <= n; i++)
- {
- if (gol2[i] == 0) continue;
- int x = pals[hs.getHash(gol2[i], gor2[i])];
- lazy[x]++;
- }
- for (int i = (int)toSortLen.size() - 1; i >= 0; i--)
- {
- int x = toSortLen[i].second;
- cnt[x] = lazy[x];
- if (parent[x] != 0)
- {
- lazy[parent[x]] += lazy[x];
- }
- }
- int sz = nextId - 1;
- for (int i = 1; i <= sz; i++)
- {
- perm[i] = i;
- }
- sort(perm + 1, perm + 1 + sz, cmpPal);
- for (int i = 1; i <= sz; i++)
- {
- sumCnt[i] = (sumCnt[i - 1] + cnt[perm[i]]);
- }
- SegmentTree st(n + 1);
- st.build(s, 1, 1, n);
- for (int i = 1; i <= q; i++)
- {
- ll x;
- scanf("%lld", &x);
- int l = 0, r = sz + 1;
- if (sumCnt[sz] < x)
- {
- puts("-1");
- continue;
- }
- while (r - l > 1)
- {
- int bm = (l + r) / 2;
- if (sumCnt[bm] < x)
- {
- l = bm;
- }
- else
- {
- r = bm;
- }
- }
- //cerr << leftPos[perm[r]] << " " << rightPos[perm[r]] << endl;
- ResultHash res = st.get(1, 1, n, leftPos[perm[r]], rightPos[perm[r]]);
- printf("%lld\n", res.value);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement