fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define itachi ios::sync_with_stdio(false); cin.tie(nullptr);
  5.  
  6. struct SegTree {
  7.     int n;
  8.     vector<ll> mn;    // min value in node
  9.     vector<int> cnt;  // count of positions attaining mn
  10.     vector<ll> lazy;  // lazy add
  11.  
  12.     SegTree(int _n=0) { init(_n); }
  13.  
  14.     void init(int _n){
  15.         n = _n;
  16.         mn.assign(4*n+5, 0);
  17.         cnt.assign(4*n+5, 0);
  18.         lazy.assign(4*n+5, 0);
  19.         if(n>0) build(1,1,n);
  20.     }
  21.  
  22.     void build(int node,int l,int r){
  23.         lazy[node]=0;
  24.         if(l==r){
  25.             mn[node]=0;
  26.             cnt[node]=1;
  27.             return;
  28.         }
  29.         int mid=(l+r)>>1;
  30.         build(node<<1,l,mid);
  31.         build(node<<1|1,mid+1,r);
  32.         pull(node);
  33.     }
  34.  
  35.     void apply(int node,ll v){
  36.         mn[node]+=v;
  37.         lazy[node]+=v;
  38.     }
  39.  
  40.     void push(int node){
  41.         if(lazy[node]!=0){
  42.             apply(node<<1, lazy[node]);
  43.             apply(node<<1|1, lazy[node]);
  44.             lazy[node]=0;
  45.         }
  46.     }
  47.  
  48.     void pull(int node){
  49.         if(mn[node<<1] < mn[node<<1|1]){
  50.             mn[node]=mn[node<<1];
  51.             cnt[node]=cnt[node<<1];
  52.         } else if(mn[node<<1] > mn[node<<1|1]){
  53.             mn[node]=mn[node<<1|1];
  54.             cnt[node]=cnt[node<<1|1];
  55.         } else {
  56.             mn[node]=mn[node<<1];
  57.             cnt[node]=cnt[node<<1] + cnt[node<<1|1];
  58.         }
  59.     }
  60.  
  61.     // add v to [L,R]
  62.     void add(int node,int l,int r,int L,int R,ll v){
  63.         if(R<l || r<L) return;
  64.         if(L<=l && r<=R){
  65.             apply(node,v);
  66.             return;
  67.         }
  68.         push(node);
  69.         int mid=(l+r)>>1;
  70.         add(node<<1,l,mid,L,R,v);
  71.         add(node<<1|1,mid+1,r,L,R,v);
  72.         pull(node);
  73.     }
  74.     void add(int L,int R,ll v){
  75.         if(L>R) return;
  76.         add(1,1,n,L,R,v);
  77.     }
  78.  
  79.     // query min and count on [L,R]
  80.     pair<ll,int> query(int node,int l,int r,int L,int R){
  81.         if(R<l || r<L) return {LLONG_MAX, 0};
  82.         if(L<=l && r<=R) return {mn[node], cnt[node]};
  83.         push(node);
  84.         int mid=(l+r)>>1;
  85.         auto a = query(node<<1,l,mid,L,R);
  86.         auto b = query(node<<1|1,mid+1,r,L,R);
  87.         if(a.first==LLONG_MAX) return b;
  88.         if(b.first==LLONG_MAX) return a;
  89.         if(a.first < b.first) return a;
  90.         if(a.first > b.first) return b;
  91.         return {a.first, a.second + b.second};
  92.     }
  93.     pair<ll,int> query(int L,int R){
  94.         if(L>R) return {LLONG_MAX,0};
  95.         return query(1,1,n,L,R);
  96.     }
  97. };
  98.  
  99. int main(){
  100.     itachi
  101.     int n, K;
  102.     if(!(cin >> n >> K)) return 0;
  103.     vector<int> a(n+1);
  104.     int maxA = 0;
  105.     for(int i=1;i<=n;i++){
  106.         cin >> a[i];
  107.         maxA = max(maxA, a[i]);
  108.     }
  109.  
  110.     // dùng map từ giá trị -> vector vị trí (0-based trong vector)
  111.     unordered_map<int, vector<int>> pos;
  112.     pos.reserve(max(1024, maxA*2+10));
  113.  
  114.     SegTree st(n);
  115.     ll ans = 0;
  116.  
  117.     for(int r=1;r<=n;r++){
  118.         int v = a[r];
  119.         auto &pv = pos[v];
  120.         pv.push_back(r); // thêm vị trí r; bây giờ m = pv.size()
  121.         int m = (int)pv.size();
  122.  
  123.         // nếu trước đó có interval không thỏa cho v (tức m-1 >= K), ta xóa nó
  124.         if(m-1 >= K){
  125.             int idx_prev = (m-1) - K; // idx_prev >= 0
  126.             int leftPrev = (idx_prev==0) ? 0 : pv[idx_prev-1];
  127.             int rightPrev = pv[idx_prev];
  128.             int Lp = leftPrev + 1;
  129.             int Rp = rightPrev;
  130.             if(Lp <= Rp) st.add(Lp, Rp, -1); // remove
  131.         }
  132.  
  133.         // nếu m >= K thì tạo interval mới [p_{m-K}+1, p_{m-K+1}] và +1
  134.         if(m >= K){
  135.             int idx = m - K; // idx >= 0
  136.             int leftPos = (idx==0) ? 0 : pv[idx-1];
  137.             int rightPos = pv[idx];
  138.             int L = leftPos + 1;
  139.             int R = rightPos;
  140.             if(L <= R) st.add(L, R, +1);
  141.         }
  142.  
  143.         // sau khi cập nhật, số l hợp lệ với r là số l in [1..r] có value == 0
  144.         auto res = st.query(1, r);
  145.         if(res.first == 0) ans += res.second;
  146.         // nếu res.first > 0 thì không có l thỏa, nếu res.first < 0 thì sai (với logic đúng không xảy ra)
  147.     }
  148.  
  149.     cout << ans << '\n';
  150.     return 0;
  151. }
  152.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/MQ162h
language:
C++14 (gcc 8.3)
created:
2 days 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!