水题一个，但是由于自己太弱还是写了很久，线段树的理解不是很好，到现在也不是很懂pushdown的精髓，只会照猫画虎，接下来的一段日子里打算做水题的同时穿插做一些数据结构。

这道题的离散化很简单，就是对于出现过的点排序即可，可以用map之类的随便搞一下，据说这个题有贪心算法，希望学习一下。最后也是压时间过得主要还是线段树理解不透彻，蒟蒻一只啊。。。

 

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include 
         
          using namespace std;const int MAX=1000000;int arr[500005][2];vector
          
            v;unordered_map
           
             mp;struct pr { int sum; int lazy; int left,right; //对应区间，注意区别rr,ll}tr[MAX+10];int n;inline int ll(int k) {return 2*k;} //左边的下标inline int rr(int k) {return 2*k+1;} //右边的下标inline int mid(int kk1,int kk2) {return (kk1+kk2)>>1;}void pushdown(int k) { if (tr[k].lazy) { //如果是加，则变成+= tr[ll(k)].sum+=tr[k].lazy*(tr[ll(k)].right-tr[ll(k)].left+1); tr[rr(k)].sum+=tr[k].lazy*(tr[rr(k)].right-tr[rr(k)].left+1); tr[ll(k)].lazy+=tr[k].lazy; tr[rr(k)].lazy+=tr[k].lazy; tr[k].lazy=0; }}void build(int k,int s,int t) { tr[k].left=s;tr[k].right=t; if(s==t) {tr[k].sum=0;return;} //开始最下面是多少 build(ll(k),s,mid(s,t)); build(rr(k),mid(s,t)+1,t); tr[k].sum=tr[ll(k)].sum+tr[rr(k)].sum; //如果是最大就是max}void modify(int k,int s,int t,int x) { int l=tr[k].left,r=tr[k].right; if(l==s&&r==t) { //(l==s&&r==t) tr[k].lazy+=x; tr[k].sum+=x*(r-l+1); return ; } pushdown(k); int mi=mid(l,r); if(t<=mi) modify(ll(k),s,t,x); else if(s>mi) modify(rr(k),s,t,x); else { modify(ll(k),s,mi,x); modify(rr(k),mi+1,t,x); } tr[k].sum=tr[ll(k)].sum+tr[rr(k)].sum;}int query(int k,int s,int t) { int l=tr[k].left,r=tr[k].right; if(l==s&&r==t) return tr[k].sum; pushdown(k); int mi=mid(l,r); int res=0; if (t<=mi) res+=query(ll(k),s,t); else if(s>mi) res+=query(rr(k),s,t); else res+=query(ll(k),s,mi)+query(rr(k),mi+1,t); return res;}int main(){ int t; cin>>t; while(t--){ cin>>n; mp.clear(); v.clear(); memset(tr,0,sizeof(tr)); for(int i=0;i
            
             ::iterator it=mp.begin(); build(1,1,nn); for(int i=0;i