求助分块
查看原帖
求助分块
302394
dingshengyang楼主2023/2/6 18:01

WA 逝怎么回逝呢?

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
const int SIZE = 316;
const int blocks = ceil((double)N/SIZE);
int n,m,L[blocks+5],R[blocks+5];
int bl[N],sorted[blocks+5][SIZE+5];
int a[N],blk,tag[blocks+5],ptr1,ptr2;
int main(){
    scanf("%d%d",&n,&m);blk = ceil((double)n /  SIZE);
    for(int i = 1;i <= n;i ++)scanf("%d",&a[i]);
    for(int i = 1;i <= blk;i ++){
        L[i] = R[i-1] + 1;
        R[i] = min(n,i * SIZE);
        for(int j = L[i];j <= R[i];j ++){
            bl[j] = i; 
            sorted[i][j-L[i]+1] = a[j];
        }
        sort(sorted[i] + 1,sorted[i]+R[i]-L[i]+1+1);
    }
    while(m --){
        int opt,l,r,k;
        scanf("%d%d%d%d",&opt,&l,&r,&k); 
        if(opt == 1){
            int p = bl[l],q = bl[r];
            long long l1 = -2147483648ll,r1 = 2147483647ll;
            if(k>r-l+1||k<1){
            	puts("-1");
            	continue;
			}
            if(p == q){
                long long ans = 0;
                while(l1 <= r1){
                    long long mid = (1ll*l1 + 1ll*r1) >> 1ll;
                    int tot = 0;
                    for(int i = l;i <= r;i ++)tot += (1ll*a[i]+tag[p]) <= mid;
                    if(tot < k)l1 = mid + 1;
                    else {
                        ans = mid;
                        r1 = mid - 1;
                    }
                }
                printf("%lld\n",ans);
            }else{
                long long ans = 0;
                while(l1 <= r1){
                    long long  mid = (1ll*l1 + 1ll*r1) >> 1ll;
                    int tot = 0;
                    for(int i = l;i <= R[p];i ++)tot += ((1ll*a[i]+tag[p]) <= mid);
                    for(int i = L[q];i <= r;i ++)tot += ((1ll*a[i]+tag[q]) <= mid);
                    for(int i = p+1;i <= q-1;i ++)
                        tot += upper_bound(sorted[i]+1,sorted[i]+(R[i]-L[i]+1)+1,mid-tag[i])-sorted[i]-1;
                    if(tot < k)l1 = mid + 1;
                    else {
                        ans = mid;
                        r1 = mid - 1;
                    }
                }
                printf("%lld\n",ans);
            }
        }else{
        	int p = bl[l],q = bl[r];
            if(p == q){
                for(int i = l;i <= r;i ++){
                    a[i] += k;
                }
                memcpy(sorted[p]+1,a+L[p],(R[p]-L[p]+1)*sizeof(int));
                sort(sorted[p]+L[p],sorted[p]+R[p]+1);
            }else{
                for(int i = l;i <= R[p];i ++)a[i] += k;
                for(int i = L[q];i <= r;i ++)a[i] += k;
                memcpy(sorted[p]+1,a+L[p],(R[p]-L[p]+1)*sizeof(int));
                memcpy(sorted[q]+1,a+L[q],(R[q]-L[q]+1)*sizeof(int));
                sort(sorted[p]+1,sorted[p]+(R[p]-L[p]+1)+1);
                sort(sorted[q]+1,sorted[q]+(R[q]-L[q]+1)+1);
                for(int i = p+1;i <= q-1;i ++)tag[i] += k;
            }
        }
//        system("pause"); 
    }
    return 0;
}   /*
10 10
15 11 -18 12 6 9 14 -2 -10 6
1 2 3 1
2 2 4 -3
1 4 10 7
1 2 2 1
1 8 8 1
2 4 10 4
1 4 10 1
1 7 10 4
2 1 4 -5
1 1 8 4
*/
2023/2/6 18:01
加载中...