分块入门三求助
  • 板块学术版
  • 楼主Alphaban
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/10/16 22:47
  • 上次更新2023/11/5 10:37:17
查看原帖
分块入门三求助
112109
Alphaban楼主2020/10/16 22:47

今天决定把分块三写掉, 结果 。。。没了 求助!

#include<stdio.h>
#include<math.h>
#include<vector>
#include<set>
#include<iostream>
#include<algorithm>
const int N = 1e5, M = 500, inf = 0x7fffffff;
using namespace std;

int n, bl[N + 5], L, v[N + 5], sum[N + 5];

vector<int > a[M + 5];

void read(int &x) {
    x = 0;char c = getchar();int w = 1;
    for(;c < '0' ||  c > '9'; c = getchar())
        if (c == '-') w = -1;
    for(; c <= '9' && c >= '0'; c = getchar())
        x = x * 10 + c - '0';
    x *= w;        
}

int max(int x, int y) {return x > y ? x : y;}
int min(int x, int y) {return x < y ? x : y ;}

void Reset(int x) {
    a[x].clear();
    for(int i = (x - 1) * L + 1; i <= min(n, x * L); ++i)
        a[x].push_back(v[i] + sum[x]);
    sort(a[x].begin(), a[x].end());    
}


void add(int l, int r, int c) {
    if (bl[l] == bl[r]) {
        for(int i = l; i <= r; ++i)
            v[i] += c;
        Reset(bl[l]);    
    }
    for(int i = l; i <= bl[l] * L; ++i)
        v[i] += c;
    Reset(bl[l]);
    for(int i = bl[l] + 1; i < bl[r]; ++i)
        sum[i] += c;
    for(int i = (bl[r] - 1) * L + 1; i <= r; ++i)
        v[i] += c;
    Reset(bl[r]);        
}

int query(int l, int r, int c) {
    int ans = -inf;
    for(int i = l; i <= bl[l] * L; ++i)
        if (v[i] + sum[bl[l]] <= c)
            ans = max(ans, v[i] + sum[bl[l]]);

    for(int i = bl[l] + 1; i < bl[r]; ++i) {
        int k = upper_bound(a[i].begin(), a[i].end(), c - sum[i]) - a[i].begin();--k;
        if (a[i][k] + sum[i] <= c)
            ans = max(ans, a[i][k] + sum[i]);
    }        
    for(int i = (bl[r] - 1) * L + 1; i <= r; ++i)
        if (v[i] + sum[bl[l]] <= c)
            ans = max(ans, v[i] + sum[bl[l]]);
     return ans == -inf ? -1 : ans;       
}

int main() {
    read(n);
    L = sqrt(n * 1.0) + .5;
    for(int i = 1; i <= n; ++i) {
        read(v[i]);
        bl[i] = (i - 1) / L + 1;
        a[bl[i]].push_back(v[i]);    
    }
    for(int i = 1; i <= bl[n]; ++i)
        sort(a[i].begin(), a[i].end());
    for(int Q = 1; Q <= n; ++Q) {
        int opt, l, r, c;
        read(opt);read(l);read(r);read(c);
        if (opt == 0) add(l, r, c);
        else printf("%d\n", query(l, r, c));
    }    
    return 0;
}
2020/10/16 22:47
加载中...