subtask1#1WA了怎么回事

duanzx @ 2024-05-18 17:59:08

#include <bits/stdc++.h>
#define vct vector
typedef long long ll;
using namespace std; 
const int N = 1e6 + 10; 
int a[N];//排序后
int b[N];//原数组 
int st[(int)2e3 + 10]; 
int ed[(int)2e3 + 10]; 
int mk[(int)2e3 + 10];
int bel[N];
int n;
bool cmp(int x, int y) {
    return x < y;
}

void Sort(int l, int r, int k) {//在一个块内从l到r加上k，再进行插入排序 
    for (int i = l; i <= r; i ++) b[i] += k;
    for (int i = l; i <= r; i ++) a[i] = b[i];
    int x = bel[l];
    sort(a + st[x], a + ed[x] + 1, cmp);//sort左闭右开 
//  vct <int> s((int)2e3 + 10, INT_MAX);
//  int l1 = 0, r1 = -1, l2 = 0, r2 = -1;
//  if (l > st[x]) l1 = st[x], r1 = l - 1;
//  if (r < ed[x]) l2 = r + 1, r2 = ed[x];
//  int pt1 = l1, ptt = l, pt2 = l2;
//  for (int i = 1; i <= ed[x] - st[x] + 1; i ++) {
//      if (pt1 <= r1) s[i] = min(s[i], a[pt1]);
//      if (ptt <= r) s[i] = min(s[i], a[ptt] + k);
//      if (pt2 <= r2) s[i] = min(s[i], a[pt2]);
//      if (s[i] == a[pt1]) pt1 ++;
//      else if (s[i] == a[ptt]) ptt ++;
//      else if (s[i] == a[pt2]) pt2 ++;
//  }
//  for (int i = 1; i <= ed[x] - st[x] + 1; i ++) {
//      a[st[x] - 1 + i] = s[i];
//  }
}

void update(int l, int r, int k) {//将l-r加上k 
    if (bel[l] == bel[r]) Sort(l, r, k);
    else {
        Sort(l, ed[bel[l]], k);
        Sort(st[bel[r]], r, k);
        for (int i = bel[l] + 1; i <= bel[r] - 1; i ++) mk[i] += k;
    }
}

int query(int l, int r, int k) {//查询l-r中多少个>=k 
    int res = 0;
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i ++) if (b[i] + mk[bel[i]] >= k) res ++;
        return res;
    }
    for (int i = l; i <= ed[bel[l]]; i ++) if (b[i] + mk[bel[i]] >= k) res ++;
    for (int i = st[bel[r]]; i <= r; i ++) if (b[i] + mk[bel[i]] >= k) res ++;
    for (int i = bel[l] + 1; i <= bel[r] - 1; i ++) {
        int lft = st[i], rit = ed[i];
        while (lft < rit) {
            int m = (lft + rit) >> 1;
            if (a[m] + mk[i] < k) lft = m + 1;
            else rit = m;
        }
        res += ed[i] - lft + 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int T;
    cin >> T;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) b[i] = a[i];
    int sq = sqrt(n);
    for (int i = 1; i <= sq; i ++) {
        st[i] = sq * (i - 1) + 1;
        ed[i] = sq * i;
    }
    ed[sq] = n;
    for (int i = 1; i <= sq; i ++) sort(a + st[i], a + ed[i] + 1, cmp);
    for (int i = 1; i <= sq; i ++) {
        for (int j = st[i]; j <= ed[i]; j ++) {
            bel[j] = i;
        }
    }
    while (T --) {
        char op;
        cin >> op;
        int l, r, c;
        cin >> l >> r >> c;
        if (op == 'M') {
            update(l, r, c);
        } else {
            cout << query(l, r, c) << '\n';
        }
    }
    return 0;
}

by OrinLoong @ 2024-07-05 13:54:51

Cuball

by OrinLoong @ 2024-07-05 14:22:39

@duanzx 调好了，你和我犯了一样的错误，看看sort函数的第二行，循环范围应该是st[bel[l]]到ed[bel[l]]

#include <bits/stdc++.h>
#define vct vector
typedef long long ll;
using namespace std; 
const int N = 1e6 + 10; 
int a[N];//排序后
int b[N];//原数组 
int st[(int)2e3 + 10]; 
int ed[(int)2e3 + 10]; 
int mk[(int)2e3 + 10];
int bel[N];
int n;
bool cmp(int x, int y) {
    return x < y;
}

void Sort(int l, int r, int k) {//在一个块内从l到r加上k，再进行插入排序 
    for (int i = l; i <= r; i ++) b[i] += k;
    for (int i = st[bel[l]]; i <= ed[bel[l]]; i ++) a[i] = b[i];//////注意这行
    int x = bel[l];
    sort(a + st[x], a + ed[x] + 1, cmp);//sort左闭右开 
//  vct <int> s((int)2e3 + 10, INT_MAX);
//  int l1 = 0, r1 = -1, l2 = 0, r2 = -1;
//  if (l > st[x]) l1 = st[x], r1 = l - 1;
//  if (r < ed[x]) l2 = r + 1, r2 = ed[x];
//  int pt1 = l1, ptt = l, pt2 = l2;
//  for (int i = 1; i <= ed[x] - st[x] + 1; i ++) {
//      if (pt1 <= r1) s[i] = min(s[i], a[pt1]);
//      if (ptt <= r) s[i] = min(s[i], a[ptt] + k);
//      if (pt2 <= r2) s[i] = min(s[i], a[pt2]);
//      if (s[i] == a[pt1]) pt1 ++;
//      else if (s[i] == a[ptt]) ptt ++;
//      else if (s[i] == a[pt2]) pt2 ++;
//  }
//  for (int i = 1; i <= ed[x] - st[x] + 1; i ++) {
//      a[st[x] - 1 + i] = s[i];
//  }
}

void update(int l, int r, int k) {//将l-r加上k 
    if (bel[l] == bel[r]) Sort(l, r, k);
    else {
        Sort(l, ed[bel[l]], k);
        Sort(st[bel[r]], r, k);
        for (int i = bel[l] + 1; i <= bel[r] - 1; i ++) mk[i] += k;
    }
}

int query(int l, int r, int k) {//查询l-r中多少个>=k 
    int res = 0;
    if (bel[l] == bel[r]) {
        for (int i = l; i <= r; i ++) if (b[i] + mk[bel[i]] >= k) res ++;
        return res;
    }
    for (int i = l; i <= ed[bel[l]]; i ++) if (b[i] + mk[bel[i]] >= k) res ++;
    for (int i = st[bel[r]]; i <= r; i ++) if (b[i] + mk[bel[i]] >= k) res ++;
    for (int i = bel[l] + 1; i <= bel[r] - 1; i ++) {
        int lft = st[i], rit = ed[i];
        while (lft < rit) {
            int m = (lft + rit) >> 1;
            if (a[m] + mk[i] < k) lft = m + 1;
            else rit = m;
        }
        res += ed[i] - lft + 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    int T;
    cin >> T;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) b[i] = a[i];
    int sq = sqrt(n);
    for (int i = 1; i <= sq; i ++) {
        st[i] = sq * (i - 1) + 1;
        ed[i] = sq * i;
    }
    ed[sq] = n;
    for (int i = 1; i <= sq; i ++) sort(a + st[i], a + ed[i] + 1, cmp);
    for (int i = 1; i <= sq; i ++) {
        for (int j = st[i]; j <= ed[i]; j ++) {
            bel[j] = i;
        }
    }
    while (T --) {
        char op;
        cin >> op;
        int l, r, c;
        cin >> l >> r >> c;
        if (op == 'M') {
            update(l, r, c);
        } else {
            cout << query(l, r, c) << '\n';
        }
    }
    return 0;
}

by duanzx @ 2024-07-05 22:22:14

@OrinLoong 非常感谢！