Untitled

 avatar
unknown
c_cpp
a month ago
1.5 kB
5
Indexable
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
const int dx[]{-1,+1,+0,+0,-1,-1,+1,+1};
const int dy[]{+0,+0,+1,-1,-1,+1,-1,+1};
const int MOD = 1e9+7;
#define int long long
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>
ordered_set;


vector<int> z_algo(string s){
    int n = s.size();
    vector<int> z(n);
    int l = 0, r = -1;
    for(int i = 1; i < n; ++i){
        if(i < r) z[i] = min(r-i, z[i-l]);
        while(i + z[i] < n && s[z[i]] == s[i+z[i]]) ++z[i];
        if(i > r){
            l = i, r = i + z[i];
        }
    }
    return z;
}

void solve(int testCase){
  int n;
  cin >> n;
  std::vector<int> v(n);
  for(int& x : v) cin >> x;
  reverse(v.begin(), v.end());
  string s = "";
  for(int i = 0; i + 1 < n; ++i){
    if(v[i] > v[i + 1]) s += 'U';
    else if(v[i] < v[i + 1]) s += 'D';
    else s += 'C';
  }
  auto z = z_algo(s);
  vector<int> d(n+1);
  for(int i = 0; i < s.size(); ++i){
    if(z[i]) d[1] += 1, d[z[i]+1] -= 1;
  }
  for(int i = 1; i < n; ++i) d[i] += d[i-1];
  int q;
  cin >> q;
  for(int i = 0; i < q; ++i){
      int x;
      cin >> x;
      cout << d[x-1] + 1 << '\n';
  }
  
}

int32_t main(){
    fastio();  
    int t = 1;
  //   cin >> t;     
    for(int i = 1; i <= t; ++i){
        solve(i);
    }
    return 0;
}
Leave a Comment