唐刚学分块1ms求调，悬五官

Rainypaster @ 2024-07-20 11:24:48

#include <bits/stdc++.h>

using namespace std;

int x;
const int N =1e6 + 5;
int pos[N], st[N], ed[N], b[N], a[N], add[N];
void update(int l, int r, int val)
{
    int p = pos[l], p1 = pos[r];
    if(p == p1)
    {
        for(int i = l;i <= r;i ++ ) a[i] += val;
        for(int i = st[p];i <= ed[p];i ++ ) b[i] = a[i];
        sort(b + st[p], b + 1 + ed[p]);
    }
    else{
        for(int i = p;i < p1;i ++ ) add[i]  += val;
        for(int i = l;i <= ed[p];i ++ ) a[i] += val;
        for(int i = st[p];i <= ed[p];i ++ ) b[i] = a[i];
        sort(b + st[p], b + 1 + ed[p]);
        for(int i = st[p1];i <= r;i ++ ) a[i] += val;
        for(int i = st[p1];i <= ed[p1];i ++ ) b[i] = a[i];
        sort(b + st[p1], b + 1 + ed[p1]);
    }
}

int mid_find(int x, int i)
{
    int l = st[i], r = ed[i];
    int ans = -1;
    while(l <= r)
    {
        int mid = (l + r)>>1;
        if(b[mid] >= x) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ed[i] - ans + 1;
}

int query(int l, int r, int x)
{
    int p = pos[l], p1 = pos[r];
    int ans = 0;
    if(p == p1)
    {
        for(int i = l;i <= r;i ++ ){
            if(a[i] + add[p] >= x) ans++ ;
        }
    }
    else {
        for(int i = p;i < p1;i ++ ) ans += mid_find(x - add[i], i);
        for(int i = l;i <= ed[p];i ++ ){
            if(a[i] + add[p] >= x) ans ++ ;
        }
        for(int i = st[p1];i <= r;i ++ ){
            if(a[i] + add[p1] >= x) ans ++ ;
        }
    }
    return ans;
}

int main()
{
    int n, q;
    cin >> n >> q;
    for(int i = 1;i <= n;i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }
    int block = sqrt(n);
    int cnt = n / block;
    if(n % block) cnt ++ ;
    for(int i = 1;i <= n;i ++ ){
        st[i] = (i - 1) * block + 1;
        ed[i] = i * block;
    }
    ed[cnt] = n;
    for(int i = 1;i <= n;i ++ ) pos[i] = (i - 1) / block + 1;
    for(int i = 1;i <= n;i ++ ) cout << st[pos[i]] << ' ' << ed[pos[i]] << endl, sort(b + st[pos[i]], b + ed[pos[i]] + 1);

    while(q -- )
    {
        char op;cin >> op;
        if(op == 'M'){
            int l, r, w;
            cin >> l >> r >> w;
            update(l, r, w);
        }
        else {
            int l, r;
            cin >>l >> r>>x;
            cout << query(l, r, x)<< endl;
        }
    }
    return 0;
}

by CNS_5t0_0r2 @ 2024-07-20 11:35:12

@Rainypaster

有这么几个问题：

1. 这里：

    for(int i = p;i < p1;i ++ ) add[i]  += val;

应该为
```cpp
for(int i = p + 1;i < p1;i ++ ) add[i]  += val;
```

2. 不开 long long 见祖宗

3. 常数太大，记得卡常

by CNS_5t0_0r2 @ 2024-07-20 11:38:16

@Rainypaster 丢一个我的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 9,SqrtN = 1e3 + 9;
int n,q;
int a[N],tmp[N];
struct block{
    int l,r,add;
} b[SqrtN];
int belong[N];
int block_cnt,block_len;
void block_sort(int block_id){
    int l = b[block_id].l,r = b[block_id].r;
    for(int i = l;i <= r;i++)
        tmp[i] = a[i];
    sort(tmp + l,tmp + r + 1);
}
void build_block(){
    block_cnt = block_len = (int)sqrt(n);
    for(int i = 1;i <= block_cnt;i++){
        b[i].l = b[i - 1].r + 1;
        b[i].r = block_len * i;
    }
    b[block_cnt].r = n;
    for(int i = 1;i <= block_cnt;i++){
        block_sort(i);
        for(int j = b[i].l;j <= b[i].r;j++)
            belong[j] = i;
    }
}
void update(int l,int r,int k){
    int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++)
            a[i] += k;
        block_sort(pos_r);
        return;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        a[i] += k;
    for(int i = b[pos_r].l;i <= r;i++)
        a[i] += k;
    for(int i = pos_l + 1;i <= pos_r - 1;i++)
        b[i].add += k;
    block_sort(pos_r);
}
int query(int l,int r,int k){
    int ret = 0;
    int pos_l = belong[l],pos_r = belong[r];
    if(pos_l == pos_r){
        for(int i = l;i <= r;i++)
            if(a[i] + b[pos_l].add >= k)
                ret++;
        return ret;
    }
    for(int i = l;i <= b[pos_l].r;i++)
        if(a[i] + b[pos_l].add >= k)
            ret++;
    for(int i = b[pos_r].l;i <= r;i++)
        if(a[i] + b[pos_r].add >= k)
            ret++;
    for(int i = pos_l + 1;i <= pos_r - 1;i++){
        int L = b[i].l,R = b[i].r;
        int pos = lower_bound(tmp + L,tmp + R + 1,k - b[i].add) - tmp;
        ret += b[i].r - pos + 1;
    }
    return ret;
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> n >> q;
    for(int i = 1;i <= n;i++)
        cin >> a[i];
    build_block();
    for(int i = 1;i <= q;i++){
        string op;
        int l,r,k;
        cin >> op >> l >> r >> k;
        if(op == "M")
            update(l,r,k);
        else
            cout << query(l,r,k) << '\n';
    }
    return 0;
}

by CNS_5t0_0r2 @ 2024-07-20 11:55:30

@Rainypaster 以下是你的全部问题：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 5;
int pos[N], st[N], ed[N], b[N], a[N], add[N];
void update(int l, int r, int val)
{
    int p = pos[l], p1 = pos[r];
    if(p == p1)
    {
        for(int i = l;i <= r;i ++ ) a[i] += val;
        for(int i = st[p];i <= ed[p];i ++ ) b[i] = a[i];
        sort(b + st[p], b + 1 + ed[p]);
    }
    else{
        for(int i = p + 1;i < p1;i ++ ) add[i]  += val;
        for(int i = l;i <= ed[p];i ++ ) a[i] += val;
        for(int i = st[p];i <= ed[p];i ++ ) b[i] = a[i];
        sort(b + st[p], b + 1 + ed[p]);
        for(int i = st[p1];i <= r;i ++ ) a[i] += val;
        for(int i = st[p1];i <= ed[p1];i ++ ) b[i] = a[i];
        sort(b + st[p1], b + 1 + ed[p1]);
    }
}

int mid_find(int x, int i)
{
    int l = st[i], r = ed[i];
    int ans = ed[i] + 1;//这里必须得是ed[i] + 1，否则会出现b中没有数大于x时返回非0的结果
    while(l <= r)
    {
        int mid = (l + r)>>1;
        if(b[mid] >= x) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return ed[i] - ans + 1;
}

int query(int l, int r, int x)
{
    int p = pos[l], p1 = pos[r];
    int ans = 0;
    if(p == p1)
    {
        for(int i = l;i <= r;i ++ ){
            if(a[i] + add[p] >= x) ans++ ;
        }
    }
    else {
        for(int i = p + 1;i < p1;i ++ ) ans += mid_find(x - add[i], i);//这里的错已经提了
        for(int i = l;i <= ed[p];i ++ ){
            if(a[i] + add[p] >= x) ans ++ ;
        }
        for(int i = st[p1];i <= r;i ++ ){
            if(a[i] + add[p1] >= x) ans ++ ;
        }
    }
    return ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n, q;
    cin >> n >> q;
    for(int i = 1;i <= n;i ++ ) {
        cin >> a[i];
        b[i] = a[i];
    }
    int block = sqrt(n);
    int cnt = n / block;
    if(n % block) cnt ++ ;
    for(int i = 1;i <= cnt;i ++ ){
        st[i] = (i - 1) * block + 1;
        ed[i] = i * block;
    }
    ed[cnt] = n;
    for(int i = 1;i <= cnt;i ++ )
        for(int j = st[i];j <= ed[i];j++)
            pos[j] = i;
    for(int i = 1;i <= cnt;i ++)sort(b + st[i], b + ed[i] + 1);//这里按照你的写法会炸

    while(q -- )
    {
        string op;cin >> op;
        if(op == "M"){
            int l, r, w;
            cin >> l >> r >> w;
            update(l, r, w);
        }
        else {
            int l, r, x;
            cin >> l >> r >> x;
            cout << query(l, r, x) << '\n';//不要用endl，常数太大
        }
    }
    return 0;
}