fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace __gnu_pbds;
  4. using namespace std;
  5.  
  6. typedef tree<int,null_type,less<int>,rb_tree_tag,
  7.         tree_order_statistics_node_update> indexed_set;
  8.  
  9. typedef long long ll;
  10. #define pb push_back
  11. #define F first
  12. #define S second
  13. #define all(v) v.begin(),v.end()
  14. #define  P pair
  15. #define V vector
  16. const long long MOD = 1000000007; // 1e9 + 7
  17.  
  18.  
  19. void file(){
  20.     freopen("input.txt.txt","r",stdin);
  21.     freopen("output.txt.txt","w",stdout);
  22. }
  23. void setio(string s) {
  24.     freopen((s + ".in").c_str(), "r", stdin);
  25.     freopen((s + ".out").c_str(), "w", stdout);
  26. }
  27. struct segtree{
  28. private:
  29.     struct node{
  30.         ll sum;
  31.     };
  32.     node neutral={0LL};
  33.     node single(ll x){
  34.         return {x};
  35.     }
  36.     node merge(node a,node b){
  37.         return{a.sum+b.sum};
  38.     };
  39. public:
  40.     int size;
  41.     V<node>query;
  42.     void init(int n){
  43.         size=1;
  44.         while(size<n)size*=2;
  45.         query.assign(2*size,neutral);
  46.     }
  47.     void build(V<ll>&a,int x,int lx,int rx){
  48.         if(rx-lx==1){
  49.             if(lx<a.size())
  50.                 query[x]=single(a[lx]);
  51.             return;
  52.         }
  53.         int m=(lx+rx)/2;
  54.         build(a,2*x+1,lx,m);
  55.         build(a,2*x+2,m,rx);
  56.         query[x]=merge(query[2*x+1],query[2*x+2]);
  57.     }
  58.     void build(V<ll>a){
  59.         build(a,0,0,size);
  60.     }
  61.     void set(ll i,ll v,int x,int lx,int rx){
  62.         if(rx-lx==1){
  63.             query[x]=single(v);
  64.             return;
  65.         }
  66.         int m=(lx+rx)/2;
  67.         if(i<m){
  68.             set(i,v,2*x+1,lx,m);
  69.         }
  70.         else
  71.             set(i,v,2*x+2,m,rx);
  72.         query[x]=merge(query[2*x+1],query[2*x+2]);
  73.     }
  74.     void set(ll i,ll v){
  75.         set(i,v,0,0,size);
  76.     }
  77.     node  calc(ll l,ll r,int x,int lx,int rx){
  78.         if(l<=lx && rx<=r)
  79.             return query[x];
  80.         if(lx>=r || rx<=l)
  81.             return neutral;
  82.         int m=(lx+rx)/2;
  83.         node a=calc(l,r,2*x+1,lx,m);
  84.         node b=calc(l,r,2*x+2,m,rx);
  85.         return merge(a,b);
  86.     }
  87.     ll calc(ll l,ll r){
  88.         return calc(l,r,0,0,size).sum;
  89.     }
  90. };
  91. struct querie{
  92.     ll f;
  93.     ll s;
  94.     ll k;
  95.     ll index;
  96. };
  97. bool maker1(querie a,querie b){
  98.     return a.f<=b.f;
  99. }
  100. bool maker2(querie a,querie b){
  101.     return a.s<=b.s;
  102. }
  103. void solve() {
  104.    ll n;
  105.    cin>>n;
  106.    ll A[n];
  107.    V<ll>compressor;
  108.    map<ll,ll>mp;
  109.    for(int i=0;i<n;i++) {
  110.        cin >> A[i];
  111.        compressor.pb(A[i]);
  112.    }
  113.    ll q;cin>>q;
  114.    querie Q[q];
  115.    for(int i=0;i<q;i++){
  116.          cin>>Q[i].f>>Q[i].s>>Q[i].k;
  117.          Q[i].f--,Q[i].s--;
  118.          compressor.pb(Q[i].k);
  119.          Q[i].index=i;
  120.    }
  121.    //start coordinate compression
  122.    sort(all(compressor));
  123.    auto it=unique(all(compressor));
  124.    compressor.resize(distance(compressor.begin(),it));
  125.    for(int i=0;i<compressor.size();i++){
  126.        mp[compressor[i]]=i;
  127.    }
  128.    for(int i=0;i<n;i++)
  129.        A[i]=mp[A[i]];
  130.    for(int i=0;i<q;i++)
  131.        Q[i].k=mp[Q[i].k];
  132.    //finish coordinate compression
  133.    //start left part computation
  134.     segtree tree;
  135.     tree.init(3e6);
  136.     P<ll,ll>ans[q];
  137.     V<ll>a(3e6);
  138.     for(int i=0;i<n;i++){
  139.         a[A[i]]++;
  140.     }
  141.     tree.build(a);
  142.     sort(Q,Q+q, maker1);
  143.     int j=0;
  144.     for(int i=0;i<n;i++){
  145.         while(Q[j].f==i && j<q){
  146.             ans[Q[j].index].F=tree.calc(Q[j].k+1,3e6);
  147.             j++;
  148.         }
  149.         a[A[i]]--;
  150.         tree.set(A[i],a[A[i]]);
  151.     }
  152.     for(int i=0;i<n;i++){
  153.         a[A[i]]++;
  154.     }
  155.     tree.build(a);
  156.     sort(Q,Q+q, maker2);
  157.     j=0;
  158.     for(int i=0;i<n;i++){
  159.         a[A[i]]--;
  160.         tree.set(A[i],a[A[i]]);
  161.         while(Q[j].s==i  && j<q){
  162.             ans[Q[j].index].S=tree.calc(Q[j].k+1,3e6);
  163.             j++;
  164.         }
  165.     }
  166.     for(int i=0;i<q;i++){
  167.         cout<<ans[i].F-ans[i].S<<endl;
  168.     }
  169. }
  170.  
  171.  
  172. int main() {
  173.     ios_base::sync_with_stdio(false);
  174.     cin.tie(NULL);
  175.     cout.tie(NULL);
  176.     //file();
  177.     solve();
  178.     return 0;
  179. }
Success #stdin #stdout 0.13s 115828KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
https://ideone.com/8Gknva
problem KQUERY, based on SPOJ submission 33052406 (CPP14-CLANG), 2024-05-16 00:08:56
language:
C++14 (clang 8.0)
created:
223 days ago
visibility:
secret

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!