社区讨论

求助DALAO!!!二分做法疯狂WA

P3939数颜色参与者 4已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi6zduin
此快照首次捕获于
2025/11/20 13:18
4 个月前
此快照最后确认于
2025/11/20 13:18
4 个月前
查看原帖
CPP
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<algorithm>
using namespace std;
const int size = 300005;

struct rabbit {
    int color, pos;
    bool operator < (const rabbit cmp) const {
        return (color == cmp.color) ? (pos < cmp.pos) : (color < cmp.color);
    }
    bool operator == (const rabbit cmp) const {
        return (color == cmp.color && pos == cmp.pos);
    }
} data[size];
int color[size];
int Find1(int l, int r, rabbit k) {
    while(l < r) {
        int mid = (l + r) / 2;
        if(data[mid] < k) l = mid + 1;
        else r = mid;
    }
    return l;
}
int Find2(int l, int r, rabbit k) {
    while(l < r) {
        int mid = (l + r + 1) / 2;
        if(data[mid] < k || data[mid] == k) l = mid;
        else r = mid - 1;
    }
    return l;
}
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i = 1;i <= n;i++) {
        scanf("%d", &color[i]);
        data[i] = (rabbit) {color[i], i};
        //printf("%d\n", data[i].color);
    }
    sort(data + 1, data + 1 + n);
//	for(int i = 1;i <= n;i++) {
//		printf("%d %d\n", data[i].color, data[i].pos);
//	}
    while(q--) {
        int man;
        scanf("%d", &man);
        if(man == 1) {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            if(l > r) {
                printf("0\n");
                continue;
            }
            int x = Find1(1, n, (rabbit) {k, l});
            int y = Find2(1, n, (rabbit) {k, r});
//			printf("%d %d\n", x, y);
            printf("%d\n", y - x + 1);
        } else {
            int i;
            scanf("%d", &i);
            if(color[i] == color[i + 1]) continue;
            int x = Find1(1, n, (rabbit) {color[i], i});
            int y = Find1(1, n, (rabbit) {color[i + 1], i + 1});
            swap(color[i], color[i + 1]);
            data[x] = (rabbit) {color[i + 1], i + 1};
            data[y] = (rabbit) {color[i], i};
//			for(int i = 1;i <= n;i++) {
//				printf("%d %d\n", data[i].color, data[i].pos);
//			}
        }
    }
    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...