Untitled
#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