fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define foru(i,a,b) for(int i=(a); i<=(b); ++i)
  5. #define ford(i,a,b) for(int i=(a); i>=(b); --i)
  6. #define rep(i,a) for(int i=0; i<(a); ++i)
  7. #define sz(a) (int)(a).size()
  8. #define all(a) (a).begin(),(a).end()
  9. #define bit(s,i) (((s)>>(i))&1)
  10. #define ii pair<int,int>
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. #define eb emplace_back
  15. #define ll long long
  16. #define _ << " " <<
  17.  
  18. template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
  19. template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
  20.  
  21. const int N=606060;
  22.  
  23. int n,q,a[N],ql[N],qr[N],ans[N];
  24.  
  25. struct PST {
  26.     struct Node {
  27.         int l, r;
  28.         int mn;
  29.         Node(): l(0), r(0), mn(0) {}
  30.     };
  31.  
  32.     int NVAL; // domain [1..NVAL]
  33.     vector<Node> seg;
  34.     vector<int> roots;
  35.  
  36.     int clone(int id) {
  37.         seg.push_back(seg[id]);
  38.         return (int)seg.size()-1;
  39.     }
  40.  
  41.     int build(int tl, int tr) {
  42.         int id = (int)seg.size();
  43.         seg.emplace_back();
  44.         if (tl == tr) {
  45.             seg[id].mn = 0;
  46.         } else {
  47.             int mid = (tl+tr)>>1;
  48.             seg[id].l = build(tl, mid);
  49.             seg[id].r = build(mid+1, tr);
  50.             seg[id].mn = 0;
  51.         }
  52.         return id;
  53.     }
  54.  
  55.     int update(int prev_id, int tl, int tr, int pos, int val) {
  56.         int id = clone(prev_id);
  57.         if (tl == tr) {
  58.             seg[id].mn = val;
  59.             return id;
  60.         }
  61.         int mid = (tl+tr)>>1;
  62.         if (pos <= mid)
  63.             seg[id].l = update(seg[prev_id].l, tl, mid, pos, val);
  64.         else
  65.             seg[id].r = update(seg[prev_id].r, mid+1, tr, pos, val);
  66.         seg[id].mn = min(seg[seg[id].l].mn, seg[seg[id].r].mn);
  67.         return id;
  68.     }
  69.  
  70.     int query_mex(int id, int tl, int tr, int threshold) {
  71.         if (seg[id].mn >= threshold) return -1;
  72.         if (tl == tr) return tl;
  73.         int mid = (tl+tr)>>1;
  74.         int res = query_mex(seg[id].l, tl, mid, threshold);
  75.         if (res != -1) return res;
  76.         return query_mex(seg[id].r, mid+1, tr, threshold);
  77.     }
  78.  
  79.     void init(int n) {
  80.         NVAL = n+1;
  81.         seg.clear(); roots.clear();
  82.         seg.reserve((n+5) * 20);
  83.         roots.reserve(n+1);
  84.         int root0 = build(1, NVAL);
  85.         roots.push_back(root0);
  86.     }
  87.  
  88.     void add_version(int val, int idx) {
  89.         int prev_root = roots.back();
  90.         int new_root = prev_root;
  91.         if (1 <= val && val <= NVAL) {
  92.             new_root = update(prev_root, 1, NVAL, val, idx);
  93.         }
  94.         roots.push_back(new_root);
  95.     }
  96.  
  97.     int get_mex(int l, int r) {
  98.         if(l > r) return -1;
  99.         int ans = query_mex(roots[r], 1, NVAL, l);
  100.         if (ans == -1) ans = NVAL+1;
  101.         return ans;
  102.     }
  103. } pst;
  104.  
  105. int mex[N],num[N],lst[N];
  106. int pos[N],curMex=1;
  107. priority_queue<ii> pq;
  108. priority_queue<ii,vector<ii>,greater<ii>> pq2;
  109.  
  110. void dnc(int l, int r, const vector<int>& qry){
  111.     if(qry.empty()) return;
  112.     if(l>r){
  113.         assert(qry.empty());
  114.         return;
  115.     }
  116.  
  117.     int m=(l+r)>>1;
  118. //    cout<<l _ r _ m<< '\n';
  119.     ford(i,m,l){
  120.         pos[a[i]]=i; if(a[i]<curMex) pq.push({pos[a[i]],a[i]});
  121.         while(pos[curMex]>0) pq.push({pos[curMex],curMex}), ++curMex;
  122.         while(pq.size() && pos[pq.top().se] != pq.top().fi) pq.pop();
  123.  
  124.         mex[i]=curMex;
  125.  
  126.         int tmp=pq.size() ? pq.top().fi+1 : i+1;
  127.         if(tmp<=m && mex[tmp]==mex[i]){
  128.             num[i]=num[tmp]+1;
  129.             lst[i]=lst[tmp];
  130.         } else{
  131.             num[i]=1;
  132.             lst[i]=tmp;
  133.         }
  134.     }
  135.     curMex=1;
  136.     foru(i,l,m) pos[a[i]]=0;
  137.     while(pq.size()) pq.pop();
  138.  
  139.     foru(i,m+1,r){
  140.         pos[a[i]]=i; if(a[i]<curMex) pq2.push({pos[a[i]],a[i]});
  141.         while(pos[curMex]>0) pq2.push({pos[curMex],curMex}), ++curMex;
  142.         while(pq2.size() && pos[pq2.top().se] != pq2.top().fi) pq2.pop();
  143.  
  144.         mex[i]=curMex;
  145.  
  146.         int tmp=pq2.size() ? pq2.top().fi-1 : i-1;
  147.         if(tmp>=m+1 && mex[tmp]==mex[i]){
  148.             num[i]=num[tmp]+1;
  149.             lst[i]=lst[tmp];
  150.         } else{
  151.             num[i]=1;
  152.             lst[i]=tmp;
  153.         }
  154.     }
  155.     curMex=1;
  156.     foru(i,m+1,r) pos[a[i]]=0;
  157.     while(pq2.size()) pq2.pop();
  158.  
  159.     vector<int> qryl, qryr;
  160.     for(auto i:qry){
  161.         int tl=ql[i], tr=qr[i];
  162.         if(tr==m){
  163.             ans[i]=num[tl];
  164.         } else if(tr<m){
  165.             qryl.eb(i);
  166.         } else if(tl>=m+1){
  167.             qryr.eb(i);
  168.         } else{
  169.             int mexlr = pst.get_mex(tl,tr);
  170.             if(mexlr==mex[tl] && mexlr==mex[tr]){
  171.                 ans[i]=num[tl]+num[tr]+(pst.get_mex(lst[tl],lst[tr]) == mexlr);
  172.             } else if(mexlr==mex[tl]){
  173.                 ans[i]=num[tl]+(pst.get_mex(lst[tl],tr) == mexlr);
  174.             } else if(mexlr==mex[tr]){
  175.                 ans[i]=num[tr]+(pst.get_mex(tl,lst[tr]) == mexlr);
  176.             } else{
  177.                 ans[i]=1;
  178.             }
  179.         }
  180.     }
  181.  
  182.     dnc(l,m-1,qryl);
  183.     dnc(m+1,r,qryr);
  184. }
  185.  
  186. void solve(){
  187.     cin>>n>>q;
  188.  
  189.     pst.init(n);
  190.     foru(i,1,n) cin>>a[i], pst.add_version(a[i],i);
  191.  
  192.     vector<int> qry;
  193.     foru(i,1,q){
  194.         cin>>ql[i]>>qr[i];
  195.         qry.eb(i);
  196.     }
  197.  
  198.     dnc(1,n,qry);
  199.  
  200.     foru(i,1,q) cout<<ans[i]<<'\n';
  201. }
  202.  
  203. int32_t main(){
  204.     #define task "test"
  205.     if(fopen(task".inp","r")){
  206.         freopen(task".inp","r",stdin);
  207.         freopen(task".out","w",stdout);
  208.     }
  209.     cin.tie(0)->sync_with_stdio(0);
  210.  
  211.     int tc=1; //cin>>tc;
  212.     rep(i,tc){
  213.         solve();
  214.     }
  215. }
  216.  
Success #stdin #stdout 0.01s 5584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/aJoZV4
language:
C++ (gcc 8.3)
created:
1 day 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!