P5356 [Ynoi2017] 由乃打扑克

我手把手教她打扑克 qwq

综合分析一下2个操作，查找区间第k小的值，感觉可以用主席树，区间修改那没事了

考虑分块做法,块长B

分析第一个操作

只需要维护数列的单调性，然后二分答案上二分就ok了

分析第二个操作

维护一个加法懒标记即可

口胡了一下感觉很简单

仔细分析一下第一个操作

二分找到一个“第k小值”，再进行check,check的过程中散块遍历一遍，整块二分找到最后一个小于等于x的（只有前面部分有贡献），分析一下时间复杂度,预处理 $O(\frac{n}{B}*BlogB)$ ,(分块完排序)，二分答案 $O(\frac{n}{B}*lognlogV)$ ,二分 $O(\frac{n}{B}*BlogB)$

第二个操作

散块可以暴力然后重构，整块上懒标记，时间复杂度 $O(\frac{n}{B}*B*logB)$

总时间复杂度 $O(m*\frac{n}{B}*lognlogV)$ maybe..

应该需要优化？

分析一下二分答案这块，我们不一定要把L定义无穷小，R定义无穷大，可以维护一下区间最大值区间最小值这样可以转化为 $O(\frac{n}{B}*logn)$ 差不多能卡过去了，我是这样干的，二分剪枝一下

分析一下散块区间加，不一定要 $O(BlogB)$ 的排序，我们可以把数列分成2块，没有加的和加的，两边其实都是有序的，因此可以用归并排序优化成 $O(B)$

快长最优可能是 $sqrt(n)logn$ ..

小优化

1.不一定要把散块重构，如果没有询问到，可以不做，我们用线段树区间赋值的思想，修改后标记一下这个块需要重构，等询问的时候问到了再进行重构

void work(int l,int r){
    int p=pos[l];
    int q=pos[r];
    for(int i=p;i<=q;i++){
        if(re[i]){
            rebuild(i);
            re[i]=0;
        }
    }
}

2.二分答案优化

    if(k<1 || R-L+1<k){
            return -1;
    }

3.块内二分优化

    if(v[id].front()+add[id]>x){//没有比x小的
        return 0;
    }
    if(v[id].back()+add[id]<=x){//都是小于等于x的
        return r+1;//r-0+1;
    }

4.维护区间最大值最小值优化

    for(int i=p+1;i<=q-1;i++){//最后一个是最大
        res=max(res,v[i].back()+add[i]);
    }
    for(int i=p+1;i<=q-1;i++){//第一个是最小
        res=min(res,v[i].front()+add[i]);
    }

完整代码

#include<iostream>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<cstring>
#include<vector>
#define INF (1ll<<60)
using namespace std;
typedef long long ll;
const int N=1e5+9;
const int B=1e4+9;
namespace Lan {
    inline string sread() {
        string s=" ";char e=getchar();
        while(e==' '||e=='\n')e=getchar();
        while(e!=' '&&e!='\n')s+=e,e=getchar();
        return s;
    }
    inline void swrite(string s){
        for(char e:s)putchar(e);
        printf("\n");
    }
    inline ll read() {
        ll x=0,y=1;char c=getchar();
        while(!isdigit(c)){if(c=='-')y=-1;c=getchar();}
        while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
        return x*=y;
    }
    inline void write(ll x) {
        if(x<0){x=-x,putchar('-');}ll sta[35],top=0;
        do sta[top++]=x%10,x/=10;while(x);
        while(top)putchar(sta[--top]+'0');
    }
}using namespace Lan;
ll a[N];
int L[B],R[B],pos[N];
ll add[B];
int re[B];
vector<ll> v[B];
inline void rebuild(int id){
    v[id].clear();
    for(int i=L[id];i<=R[id];i++){
        v[id].push_back(a[i]);
    }
    sort(v[id].begin(),v[id].end());
}
inline int binary(int id,int x){
    int l=0,r=v[id].size()-1;
    if(v[id].front()+add[id]>x){//没有比x小的
        return 0;
    }
    if(v[id].back()+add[id]<=x){//都是小于等于x的
        return r+1;//r-0+1;
    }
    int res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(v[id][mid]+add[id]<=x){//小于等于x，选大一点
            l=mid+1;
            res=mid+1;//小于等于x的有贡献
        }else{
            r=mid-1;
        }
    }
    return res;
}
inline ll getmax(int l,int r){
    ll res=-INF;
    int p=pos[l];
    int q=pos[r];
    if(p==q){
        for(int i=l;i<=r;i++){
            res=max(res,a[i]+add[pos[i]]);
        }
    }else{
        for(int i=l;i<=R[p];i++){
            res=max(res,a[i]+add[pos[i]]);
        }
        for(int i=L[q];i<=r;i++){
            res=max(res,a[i]+add[pos[i]]);
        }
        for(int i=p+1;i<=q-1;i++){//最后一个是最大
            res=max(res,v[i].back()+add[i]);
        }
    }   
    return res;
}
inline ll getmin(int l,int r){
    ll res=INF;
    int p=pos[l];
    int q=pos[r];
    if(p==q){
        for(int i=l;i<=r;i++){
            res=min(res,a[i]+add[pos[i]]);
        }
    }else{
        for(int i=l;i<=R[p];i++){
            res=min(res,a[i]+add[pos[i]]);
        }
        for(int i=L[q];i<=r;i++){
            res=min(res,a[i]+add[pos[i]]);
        }
        for(int i=p+1;i<=q-1;i++){//第一个是最小
            res=min(res,v[i].front()+add[i]);
        }
    }
    return res;
}
inline int check(int l,int r,int x){
    int p=pos[l];
    int q=pos[r];
    int res=0;
    if(p==q){
        for(int i=l;i<=r;i++){
            if(a[i]+add[pos[i]]<=x){
                res++;
            }
        }
    }else{
        for(int i=l;i<=R[p];i++){
            if(a[i]+add[pos[i]]<=x){
                res++;
            }
        }
        for(int i=L[q];i<=r;i++){ 
            if(a[i]+add[pos[i]]<=x){
                res++;
            }
        }
        for(int i=p+1;i<=q-1;i++){
            res+=binary(i,x);
        }
    }
    return res;
}
void work(int l,int r){
    int p=pos[l];
    int q=pos[r];
    for(int i=p;i<=q;i++){
        if(re[i]){
            rebuild(i);
            re[i]=0;
        }
    }
}
inline int kth(int k,int L,int R){
    if(k<1 || R-L+1<k){
        return -1;
    }
    work(L,R);
    int res=-1;
    ll l=getmin(L,R),r=getmax(L,R);
    while(l<=r){
        ll mid=(l+r)>>1;
        if(check(L,R,mid)<k){//选的值太小
            l=mid+1;
        }else{
            r=mid-1;
            res=mid;
        }
    }
    return res;
}
inline void modify(int l,int r,int k){
    int p=pos[l];
    int q=pos[r];
    if(p==q){
        for(int i=l;i<=r;i++){
            a[i]+=k;
        }
        re[p]=1;
        // rebuild(p);
    }else{
        for(int i=l;i<=R[p];i++){
            a[i]+=k;
        }
        re[p]=1;
        // rebuild(p);
        for(int i=p+1;i<=q-1;i++){
            add[i]+=k;
        }
        for(int i=L[q];i<=r;i++){
            a[i]+=k;
        }
        re[q]=1;
        // rebuild(q);
    }
}
int main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    int n,m;
    n=read();
    m=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int blo=sqrt(n);
    int t=ceil(1.0*n/blo);
    for(int i=1;i<=t;i++){
        L[i]=(i-1)*blo+1;
        R[i]=(i==t?n:i*blo);
    }
    for(int i=1;i<=t;i++){
        for(int j=L[i];j<=R[i];j++){
            pos[j]=i;
        }
    }
    for(int i=1;i<=n;i++){
        v[pos[i]].push_back(a[i]);
    }
    for(int i=1;i<=t;i++){
        sort(v[i].begin(),v[i].end());
    }
    for(int i=1;i<=m;i++){
        int op,l,r,k;
        op=read();
        l=read();
        r=read();
        k=read();
        if(op==1){
            write(kth(k,l,r));
            putchar('\n');
        }else{
            modify(l,r,k);
        }
    }
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/530791.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！