fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef pair<int, int> pii;
  5. typedef pair<ll, ll> pll;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vll;
  8. #define pb push_back
  9. #define ff first
  10. #define ss second
  11.  
  12. const int N = 1024 * 1024;
  13. ll tree[2 * N][3];
  14.  
  15. struct quer{
  16.     int l, r, ind;
  17. };
  18.  
  19. void upd(int v, ll val, int t){
  20.     v += N;
  21.     while(v) {
  22.         tree[v][t] += val;
  23.         v >>= 1;
  24.     }
  25. }
  26.  
  27. ll query(int l, int r, int t){
  28.     l += N;
  29.     r += N;
  30.     ll wyn = 0;
  31.     while(l <= r) {
  32.         if(l & 1) wyn += tree[l++][t];
  33.         if(!(r & 1)) wyn += tree[r--][t];
  34.         l >>= 1; r >>= 1;
  35.     }
  36.     return wyn;
  37. }
  38.  
  39. int main() {
  40.     ios_base::sync_with_stdio(0);
  41.     cin.tie(0);
  42.  
  43.     int n, q;
  44.     cin >> n >> q;
  45.  
  46.     string s, t = "^#";
  47.     cin >> s;
  48.     for(char c : s){
  49.         t += c;
  50.         t += '#';
  51.     }
  52.     t += '$';
  53.  
  54.     int m = t.size();
  55.     vi p(m, 0);
  56.     int g = 0, manacher = 0;
  57.  
  58.     for(int i = 1; i < m - 1; i++){
  59.         int odwr = 2 * g - i;
  60.         if(manacher > i){
  61.             p[i] = min(manacher - i, p[odwr]);
  62.         }else{
  63.             p[i] = 0;
  64.         }
  65.         while(t[i + 1 + p[i]] == t[i - 1 - p[i]]) p[i]++;
  66.  
  67.         if(i + p[i] > manacher) {
  68.             g = i;
  69.             manacher = i + p[i];
  70.         }
  71.     }
  72.  
  73.     vi pr(2 * n + 1), cl(2 * n + 1), cr(2 * n + 1), grl(2 * n + 1), grr(2 * n + 1);
  74.     for(int x = 2; x <= 2 * n; x++){
  75.         cl[x] = x / 2;
  76.         cr[x] = (x + 1) / 2;
  77.         pr[x] = (p[x] + 1) / 2;
  78.         grl[x] = cl[x] - pr[x];
  79.         grr[x] = cr[x] + pr[x];
  80.     }
  81.  
  82.     vector<vector<quer>> ql(n + 1), qr(n + 1);
  83.     for(int i = 0; i < q; i++){
  84.         int l, r;
  85.         cin >> l >> r;
  86.         ql[l].pb({l, r, i});
  87.         qr[r].pb({l, r, i});
  88.     }
  89.  
  90.     vll wyn(q, 0);
  91.     vector<vi> el(n + 2);
  92.  
  93.     for(int x = 2; x <= 2 * n; x++){
  94.         upd(x, cl[x] + 1, 1);
  95.         upd(x, 1, 2);
  96.  
  97.         int tr = grl[x] + 1;
  98.         if(tr > n) tr = n + 1;
  99.         if(tr >= 1) el[tr].pb(x);
  100.     }
  101.  
  102.     for(int aktl = n + 1; aktl >= 1; aktl--){
  103.         for(int x : el[aktl]) {
  104.             upd(x, -(cl[x] + 1), 1);
  105.             upd(x, -1, 2);
  106.             upd(x, pr[x], 0);
  107.         }
  108.  
  109.         if(aktl <= n){
  110.             for(auto &zap : ql[aktl]){
  111.                 int aktr = zap.r;
  112.                 ll s1 = query(2 * aktl, aktl + aktr, 0);
  113.                 ll s2c = query(2 * aktl, aktl + aktr, 1);
  114.                 ll s2cnt = query(2 * aktl, aktl + aktr, 2);
  115.  
  116.                 wyn[zap.ind] += s1 + s2c - 1ll * aktl * s2cnt;
  117.             }
  118.         }
  119.     }
  120.  
  121.     vector<vi> er(n + 1);
  122.  
  123.     for(int i = 0; i < 2 * N; i++){
  124.     	tree[i][0] = 0; tree[i][1] = 0; tree[i][2] = 0;
  125.     }
  126.  
  127.     for(int x = 2; x <= 2 * n; x++){
  128.         upd(x, cr[x] - 1, 1);
  129.         upd(x, 1, 2);
  130.  
  131.         int tr = grr[x] - 1;
  132.         if(tr < 0) tr = 0;
  133.         if(tr <= n) er[tr].pb(x);
  134.     }
  135.  
  136.     for(int aktr = 0; aktr <= n; aktr++){
  137.         for(int x : er[aktr]){
  138.             upd(x, -(cr[x] - 1), 1);
  139.             upd(x, -1, 2);
  140.             upd(x, pr[x], 0);
  141.         }
  142.  
  143.         if(aktr >= 1){
  144.             for(auto &zap : qr[aktr]){
  145.                 int aktl = zap.l;
  146.                 ll s1 = query(aktl + aktr + 1, 2 * aktr, 0);
  147.                 ll s2c = query(aktl + aktr + 1, 2 * aktr, 1);
  148.                 ll s2cnt = query(aktl + aktr + 1, 2 * aktr, 2);
  149.  
  150.                 wyn[zap.ind] += s1 + 1LL * aktr * s2cnt - s2c;
  151.             }
  152.         }
  153.     }
  154.  
  155.     for(int i = 0; i < q; i++){
  156.         cout << wyn[i] << "\n";
  157.     }
  158.  
  159.     return 0;
  160. }
Success #stdin #stdout 0.01s 52700KB
comments (?)
stdin
copy 
10 8
abaabcbaab
3 7
2 7
8 9
3 10
1 3
1 10
4 8
2 9
stdout
copy 
7
9
3
14
4
19
7
14
https://ideone.com/qP8hfp
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!