T4提高小班求救

问题讨论区 提高段
1

image

#include <bits/stdc++.h>
#define int long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
struct node{
	int l,r,sum;
}tr[800005];
int p[600005],s[600005];
char t[600005];
int a[600005],b[600005];
int uni[600005],cnt,pt;
void build(int p,int l,int r){
	tr[p].l=l;
	tr[p].r=r;
	tr[p].sum=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
}
void update(int p,int pos,int d){
	if(tr[p].l==tr[p].r){
		tr[p].sum+=d;
		return;
	}
	int mid=(tr[p].l+tr[p].r)>>1;
	if(pos<=mid) update(lc,pos,d);
	else update(rc,pos,d);
	tr[p].sum=tr[lc].sum+tr[rc].sum;
}
int query(int p,int x,int y){
	if(x>tr[p].r||y<tr[p].l) return 0;
	if(x<=tr[p].l&&tr[p].r<=y) return tr[p].sum;
	return query(lc,x,y)+query(rc,x,y);
}
inline int gd(int x){
	return lower_bound(uni+1,uni+pt+1,x)-uni;
}
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>>p[i];
		s[++cnt]=p[i];
	}
	for(int i=1;i<=q;i++){
		cin>>t[i]>>a[i]>>b[i];
		if(t[i]=='!'){
			s[++cnt]=b[i];
		}else{
			s[++cnt]=a[i];
			s[++cnt]=b[i];
		}
	}
	sort(s+1,s+cnt+1);
	pt=unique(s+1,s+cnt+1)-s-1;
	for(int i=1;i<=pt;i++){
		uni[i]=s[i];
	}
	build(1,1,pt);
	for(int i=1;i<=n;i++){
		update(1,gd(p[i]),1);
	}
	for(int i=1;i<=q;i++){
		if(t[i]=='!'){
			int k=a[i],x=b[i];
			update(1,gd(p[k]),-1);
			p[k]=x;
			update(1,gd(p[k]),1);
		}else{
			int l=gd(a[i]);
			int r=gd(b[i]);
			cout<<query(1,l,r)<<"\n";
		}
	}
}

TLE60分
@俞天行

1 个赞
2

刚回家qaq

3

Let me see。。。

1 个赞
4

还在吗 \texttt{QwQ}

我先走了

1 个赞
5

额，我来看看哈

6

题号多少？

7

离散化处理的不够吧

8

我优化了一个代码


#include <bits/stdc++.h>

using namespace std;

const int MAXN = 6e5 + 10; // 扩大离散化容量

struct Node {
    int l, r, cnt;
} tr[MAXN << 2];  // 扩大线段树容量

vector<int> nums; // 离散化数组
int p[MAXN], orig[MAXN];

// 离散化压缩函数
inline int get_id(int x) {
    return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
}

void build(int p, int l, int r) {
    tr[p] = {l, r, 0};
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
}

void update(int p, int pos, int val) {
    if (tr[p].l == tr[p].r) {
        tr[p].cnt += val;
        return;
    }
    int mid = (tr[p].l + tr[p].r) >> 1;
    if (pos <= mid) update(p<<1, pos, val);
    else update(p<<1|1, pos, val);
    tr[p].cnt = tr[p<<1].cnt + tr[p<<1|1].cnt;
}

int query(int p, int l, int r) {
    if (tr[p].r < l || tr[p].l > r) return 0;
    if (l <= tr[p].l && tr[p].r <= r) return tr[p].cnt;
    return query(p<<1, l, r) + query(p<<1|1, l, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, q;
    cin >> n >> q;
    
    // 收集所有可能的值
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
        nums.push_back(p[i]);
        orig[i] = p[i];
    }
    
    vector<tuple<char, int, int>> queries;
    for (int i = 0; i < q; ++i) {
        char op;
        int a, b;
        cin >> op >> a >> b;
        queries.emplace_back(op, a, b);
        if (op == '!') {
            nums.push_back(b);
        } else {
            nums.push_back(a);
            nums.push_back(b);
        }
    }
    
    // 离散化处理
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    int m = nums.size();
    build(1, 1, m);
    
    // 初始化线段树
    for (int i = 1; i <= n; ++i) {
        int pos = get_id(p[i]);
        update(1, pos, 1);
    }
    
    // 处理查询
    for (auto& [op, a, b] : queries) {
        if (op == '!') {
            int k = a;
            int old_pos = get_id(orig[k]);
            update(1, old_pos, -1);
            
            orig[k] = b;
            int new_pos = get_id(b);
            update(1, new_pos, 1);
        } else {
            int L = lower_bound(nums.begin(), nums.end(), a) - nums.begin() + 1;
            auto it = upper_bound(nums.begin(), nums.end(), b);
            int R = it - nums.begin(); // upper_bound返回的是超尾位置
            
            if (L > R) {
                cout << "0\n";
            } else {
                cout << query(1, L, R) << "\n";
            }
        }
    }
    
    return 0;
}

警告：请勿直接提交，已经过伪装AI处理

9

那我让Deepseek把AI还原了你不炸了吗

1 个赞
10

不行啊，加英文翻译就对胃了

11

过了吗？

12

你给我解释一下被

1 个赞
13

行的

14

过了没？

15

你给我解释一下。。。

1 个赞
16

解释啥？。

17

哦哦哦。。。

  • 使用lower_bound确定左边界

  • 使用upper_bound确定右边界（返回超尾位置）

  • 当L > R时直接返回0

18

然后把数组换成了vector会更快一点

19

当我打开洛谷，发现一些犇犇……
0