Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MV 300001
- #define pb push_back
- struct cap
- {
- int lb, rb, md;
- std::map<int, int> ctr;
- }seg[4*MV];
- int arr[MV];
- std::vector<int> Z;
- class segtree
- {
- public: void build(int i, int s, int d);
- cap merger(cap left, cap right);
- void update(int i, int s, int d, int x, int y);
- void query(int i, int s, int d, int qs, int qd);
- };
- void segtree::build(int i, int s, int d)
- {
- if(s == d)
- {
- seg[i].lb = s;
- seg[i].rb = d;
- seg[i].md = arr[s];
- seg[i].ctr[arr[s]]++;
- return;
- }
- int m = (s + d)/2;
- build(2*i, s, m);
- build(2*i+1, m+1, d);
- seg[i] = merger(seg[2*i], seg[2*i+1]);
- return;
- }
- cap segtree::merger(cap left, cap right)
- {
- cap res;
- if(!left.lb)
- {
- res.lb = right.lb;
- res.rb = right.rb;
- }
- else if(!right.lb)
- {
- res.lb = left.lb;
- res.rb = left.rb;
- }
- else
- {
- res.lb = left.lb;
- res.rb = right.rb;
- }
- res.ctr.insert(left.ctr.begin(), left.ctr.end());
- for(std::map<int, int>::iterator it = right.ctr.begin();it != right.ctr.end();it++)
- res.ctr[it->first] += right.ctr[it->first];
- res.md = 0;
- if(left.md)
- {
- if((res.ctr[left.md])*2 > (res.rb - res.lb + 1))
- res.md = left.md;
- }
- if(right.md)
- {
- if((res.ctr[right.md])*2 > (res.rb - res.lb + 1))
- res.md = right.md;
- }
- return res;
- }
- void segtree::query(int i, int s, int d, int qs, int qd)
- {
- if(s > qd || d < qs)
- return;
- if(qs <= s && d <= qd)
- {
- Z.pb(i);
- return;
- }
- int m = (s + d)/2;
- query(2*i, s, m, qs, qd);
- query(2*i+1, m+1, d, qs, qd);
- return;
- }
- int main(void)
- {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(NULL);
- std::cout.tie(NULL);
- int n,c;
- std::cin>>n>>c;
- for(int i=1;i<=n;i++)
- std::cin>>arr[i];
- segtree T;
- T.build(1, 1, n);
- int q;
- std::cin>>q;
- while(q--)
- {
- Z.clear();
- int l,r;
- std::cin>>l>>r;
- T.query(1, 1, n, l, r);
- bool ok = 0;
- for(int i=0,t=(int)Z.size();i<t;i++)
- {
- int ct = 0;
- if(seg[Z[i]].md)
- {
- for(int j=0;j<t;j++)
- ct += seg[Z[j]].ctr[seg[Z[i]].md];
- }
- if(ct*2 > (r-l+1))
- {
- std::cout<<"yes "<<seg[Z[i]].md<<"\n";
- ok = 1;
- break;
- }
- }
- if(!ok)
- std::cout<<"no\n";
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment