【题目分析】

    整体二分显而易见。

    自己YY了一下用树状数组区间修改，区间查询的操作。

    又因为一个字母调了一下午。

    貌似树状数组并不需要清空，可以用一个指针来维护，可以少一个log

    懒得写了。

【代码】

#include 
     
      #include 
      
       #include 
       
        #include 
        
           using namespace std;  #define maxn 50005#define inf 0x3f3f3f3f#define ll long long   ll n,m,cnt=0,tot=0;  struct Bit_Tree{    ll a[maxn],b[maxn];    void add(ll x,ll y,ll z)    {//      cout<<"Add "<
         
          <<" "<
          
           <<" "<
           
            <
            
             qr) return; if (l==r) { for (ll i=ql;i<=qr;++i) ans[q[i].id]=l; return ; } ll mid=l+r>>1,p1=0,p2=0,cnt=0;// cout<<"Mid is "<
             
              <