fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define maxn 100005
  5. using namespace std;
  6.  
  7. const int MAXV = 200005;
  8. const int OFF_NEG = 100002;
  9. const int OFF_POS = 0;
  10. const int MAXNODE = 8000005;
  11.  
  12. int n, q;
  13. string s;
  14.  
  15. // ===== PST =====
  16. int Lson[MAXNODE], Rson[MAXNODE];
  17. ll cnt[MAXNODE], sumv[MAXNODE];
  18. int root[4][maxn];
  19. int node = 0;
  20.  
  21. int new_node(int pre){
  22.     int id = ++node;
  23.     Lson[id] = Lson[pre];
  24.     Rson[id] = Rson[pre];
  25.     cnt[id] = cnt[pre];
  26.     sumv[id] = sumv[pre];
  27.     return id;
  28. }
  29.  
  30. int build(int l,int r){
  31.     int id = ++node;
  32.     if(l==r) return id;
  33.     int m=(l+r)>>1;
  34.     Lson[id]=build(l,m);
  35.     Rson[id]=build(m+1,r);
  36.     return id;
  37. }
  38.  
  39. int update(int pre,int l,int r,int pos,ll val){
  40.     int id = new_node(pre);
  41.     cnt[id]++;
  42.     sumv[id]+=val;
  43.     if(l==r) return id;
  44.     int m=(l+r)>>1;
  45.     if(pos<=m) Lson[id]=update(Lson[pre],l,m,pos,val);
  46.     else Rson[id]=update(Rson[pre],m+1,r,pos,val);
  47.     return id;
  48. }
  49.  
  50. pair<ll,ll> get(int u,int v,int l,int r,int lim){
  51.     if(l>lim) return {0,0};
  52.     if(r<=lim) return {cnt[v]-cnt[u], sumv[v]-sumv[u]};
  53.     int m=(l+r)>>1;
  54.     auto L = get(Lson[u],Lson[v],l,m,lim);
  55.     if(lim>m){
  56.         auto R = get(Rson[u],Rson[v],m+1,r,lim);
  57.         L.first += R.first;
  58.         L.second += R.second;
  59.     }
  60.     return L;
  61. }
  62.  
  63. // ===== utils =====
  64. ll sum_arith(ll L,ll R){
  65.     if(L>R) return 0;
  66.     return (L+R)*(R-L+1)/2;
  67. }
  68.  
  69. // ===== Manacher =====
  70. int d1[maxn], d2[maxn];
  71.  
  72. void manacher(){
  73.     string t="$#";
  74.     for(char c: s){
  75.         t+=c; t+='#';
  76.     }
  77.     t+="^";
  78.  
  79.     int m=t.size();
  80.     vector<int> P(m);
  81.     int C=0,R=0;
  82.  
  83.     for(int i=1;i<m-1;i++){
  84.         int mir=2*C-i;
  85.         if(i<R) P[i]=min(R-i,P[mir]);
  86.         while(t[i+1+P[i]]==t[i-1-P[i]]) P[i]++;
  87.         if(i+P[i]>R){
  88.             C=i; R=i+P[i];
  89.         }
  90.     }
  91.  
  92.     for(int i=1;i<=n;i++){
  93.         d1[i]=(P[2*i]+1)/2;
  94.         if(i<n) d2[i]=P[2*i+1]/2;
  95.     }
  96. }
  97.  
  98. int main(){
  99.     itachi
  100.  
  101.     cin>>n>>q>>s;
  102.  
  103.     manacher();
  104.  
  105.     int base = build(1,MAXV);
  106.     for(int i=0;i<4;i++) root[i][0]=base;
  107.  
  108.     // ===== build PST =====
  109.  
  110.     for(int i=1;i<=n;i++){
  111.         int A1 = d1[i]-i;
  112.         int A2 = d1[i]+i;
  113.  
  114.         root[0][i]=update(root[0][i-1],1,MAXV,A1+OFF_NEG,A1);
  115.         root[1][i]=update(root[1][i-1],1,MAXV,A2+OFF_POS,A2);
  116.     }
  117.  
  118.     for(int i=1;i<n;i++){
  119.         int B1 = d2[i]-i;
  120.         int B2 = d2[i]+i;
  121.  
  122.         root[2][i]=update(root[2][i-1],1,MAXV,B1+OFF_NEG,B1);
  123.         root[3][i]=update(root[3][i-1],1,MAXV,B2+OFF_POS,B2);
  124.     }
  125.  
  126.     // ===== queries =====
  127.     while(q--){
  128.         int l,r;
  129.         cin>>l>>r;
  130.         ll ans=0;
  131.  
  132.         // ---- odd ----
  133.         int mid=(l+r)>>1;
  134.  
  135.         if(l<=mid){
  136.             int L=l,R=mid;
  137.             int lim=1-l;
  138.             auto res=get(root[0][L-1],root[0][R],1,MAXV,lim+OFF_NEG);
  139.             ans += res.second + (R-L+1-res.first)*lim + sum_arith(L,R);
  140.         }
  141.  
  142.         if(mid+1<=r){
  143.             int L=mid+1,R=r;
  144.             int lim=r+1;
  145.             auto res=get(root[1][L-1],root[1][R],1,MAXV,lim+OFF_POS);
  146.             ans += res.second + (R-L+1-res.first)*lim - sum_arith(L,R);
  147.         }
  148.  
  149.         // ---- even ----
  150.         int mid2=(l+r-1)>>1;
  151.  
  152.         if(l<=mid2){
  153.             int L=l,R=mid2;
  154.             int lim=1-l;
  155.             auto res=get(root[2][L-1],root[2][R],1,MAXV,lim+OFF_NEG);
  156.             ans += res.second + (R-L+1-res.first)*lim + sum_arith(L,R);
  157.         }
  158.  
  159.         if(mid2+1<=r-1){
  160.             int L=mid2+1,R=r-1;
  161.             int lim=r;
  162.             auto res=get(root[3][L-1],root[3][R],1,MAXV,lim+OFF_POS);
  163.             ans += res.second + (R-L+1-res.first)*lim - sum_arith(L,R);
  164.         }
  165.  
  166.         cout<<ans<<"\n";
  167.     }
  168. }
Success #stdin #stdout 0.01s 13856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UZYHtY
language:
C++14 (gcc 8.3)
created:
10 hours 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!