题目大意:

题解:

我们发现这道题其实是两问

第一问是对于 \(R, C\leq 200,M\leq 200,000\)

是在矩形上的询问

第二问是对于 \(R＝1,C\leq 500,000,M\leq 20,000\)

是在序列上的询问

所以我们写两个程序即可

首先我们来解决序列上的问题:

很明显我们在主席树上二分查找即可.\(O(mlogn)\)可做

然后我们来解决在矩形上的问题:

很明显我们写个二维差分主席树就好了啦

我们发现这个子任务的特点是R,C的范围很小所以我们考虑预处理

我们可以预处理出\(f[i][j][k]\)表示在二维前缀和\((i,j)\)中

大于等于\(k\)的数的和,这样我们就可以二分啦！

同时为了统计答案我们还要处理出\(g[i][j][k]\)表示>=k的数的个数

然后这道题就华丽丽地解决啦

我们还有一个问题!

对于序列:2 2 2 2我们取多少才能达到高度\(2\),很明显取1个

但是程序会输出4

这个东西再二分一下还应该删除多少个不久好了吗。。。

竟然1A了

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;inline void read(int &x){    x=0;char ch;bool flag = false;    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a
       > 1;                if(calc_f(mid) >= h) ans = mid,l = mid+1;                else r = mid-1;            }if(ans == -1) puts("Poor QLW");            else{                int x = calc_f(ans) - calc_f(ans+1);x /= ans;                int y = calc_g(ans);                int z = calc_f(ans);                l = 0,r = x;x = 0;                while(l <= r){                    int mid = (l+r) >> 1;                    if(z - mid*ans >= h) x = mid,l = mid+1;                    else r = mid-1;                }y -= x;                printf("%d\n",y);            }        }        return 0;    }}namespace work2{    const int maxn = 500010;    typedef pair
        
          pa;    struct Node{        Node *ch[2];        int sum,num;    }*null;    inline void init(){        null = new Node;        null->ch[0] = null->ch[1] = null;        null->sum = null->num = 0;    }    Node *rt[maxn];    inline Node* insert(Node *rt,int l,int r,int val){        Node *p = new Node();(*p) = (*rt);        if(l == r){            p->sum += val;            p->num ++ ;            return p;        }int mid = (l+r) >> 1;        if(val <= mid) p->ch[0] = insert(rt->ch[0],l,mid,val);        else p->ch[1] = insert(rt->ch[1],mid+1,r,val);        p->sum = p->ch[0]->sum + p->ch[1]->sum;        p->num = p->ch[0]->num + p->ch[1]->num;        return p;    }int pos = -1,cnt = -1;    inline pa query(Node *x,Node *y,int l,int r,int h){        if(l == r){            pos = l;cnt = y->num - x->num;            return make_pair(y->sum - x->sum,y->num - x->num);        }        int mid = (l+r) >> 1,sum = y->ch[1]->sum - x->ch[1]->sum;        if(sum < h){            pa tmp = query(x->ch[0],y->ch[0],l,mid,h-sum);            tmp.first += y->ch[1]->sum - x->ch[1]->sum;            tmp.second += (y->ch[1]->num - x->ch[1]->num);            return tmp;        }else return query(x->ch[1],y->ch[1],mid+1,r,h);    }    int main(){        init();n = m;rt[0] = null;        for(int i=1,x;i<=n;++i){            read(x);            rt[i] = insert(rt[i-1],1,1000,x);        }        while(q--){            int s,t;read(s);read(s);read(t);read(t);            int h;read(h);            pa x = query(rt[s-1],rt[t],1,1000,h);            if(x.first < h){puts("Poor QLW");continue;}            int l = 0,r = cnt,y = 0;            while(l <= r){                int mid = (l+r) >> 1;                if(x.first - mid*pos >= h) y = mid,l = mid+1;                else r = mid-1;            }            printf("%d\n",x.second - y);        }        return 0;    }}int main(){    read(n);read(m);read(q);    if(n != 1) work1::main();    else work2::main();    getchar();getchar();    return 0;}
        
      
     
    

不得不说当时我开数组的时候浑身难受

一两个数组就100多MB下去了...