信息学奥赛社区

你的代码中存在几个关键问题导致死机，以下是详细分析和修复方案： 
 
 问题1：主函数初始化循环导致死循环 
 // 错误代码片段
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) {  // 循环次数被动态修改的n影响
    add_num(tmp);        // add_num内部有n++
}
 
 问题分析 ：初始化时， add_num 中的 n++ 会动态修改循环变量 n ，导致循环次数远超预期（例如输入n=3时实际循环次数会无限增加）。 
 解决方案 ：用固定值控制循环次数： 
 int initial_n = n;  // 保存原始输入值
for(int i=1; i<=initial_n; i++) {
    // ... 其他代码不变
}
 
 
 问题2：删除不存在的元素导致数组越界 
 // 错误代码片段
if(p==2) {
    tong[k]--;  // 可能导致负数
    add1(tong[k],1);  // 可能操作下标0或负数
}
 
 问题分析 ：当 tong[k] 已经是0时继续删除，会导致 tong[k] 变为负数，后续对树状数组的操作会访问非法内存。 
 解决方案 ：添加删除前的合法性检查： 
 if(p==2) {
    if(tong[k] <= 0) {  // 防御性判断
        printf("Error: Cannot delete non-existent element\n");
        continue;
    }
    // ... 原删除逻辑
}
 
 
 问题3：树状数组操作下标越界 
 问题分析 ：树状数组操作函数未对下标做校验，可能传入0或负数导致死循环。 
 修复方案 ：在操作函数开头添加边界检查： 
 void add1(int x,int y) {
    if(x <= 0) return;  // 关键修复！
    while(x <= N-10) {
        c1[x] += y;
        x += lowbit(x);
    }
}
// add2函数同理添加校验
 
 
 其他关键修改 
 
 
 移除 add_num 中的 n++ ： 
 void add_num(int v) {
    // n++;  // 此行需删除
    if(!tong[v]) num++;
    tong[v]++;
}
 
 
 
 手动维护 n 的正确性 ： 
 if(p==1) {
    add_num(k);
    n++;  // 手动增加元素总数
    // ... 其他逻辑
}
 
 
 
 
 修复后的完整代码 
 已将所有关键修复整合到代码中，请参考以下完整版本： 
 #include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int n,q;
ll num=0;
ll c1[N],c2[N];//num,weight
ll tong[N];

int lowbit(int x) { return x&-x; }

void add1(int x,int y) {
    if(x <=0) return; // 修复：防止非法下标
    while(x<=N-10) {
        c1[x]+=y;
        x+=lowbit(x);
    } 
}

void add2(int x,int y) {
    if(x <=0) return; // 修复：防止非法下标
    while(x<=N-10) {
        c2[x]+=y;
        x+=lowbit(x);
    } 
}

ll ask1(int x) {
    ll ans=0;
    while(x>0) {
        ans+=c1[x];
        x-=lowbit(x);
    }
    return ans;
}

ll ask2(int x) {
    ll ans=0;
    while(x>0) {
        ans+=c2[x];
        x-=lowbit(x);
    }
    return ans;
}

void add_num(int v) {
    if(!tong[v]) num++;
    tong[v]++; 
}

int main() {
    scanf("%d%d",&n,&q);
    int initial_n = n; // 修复：用固定值控制循环
    for(int i=1;i<=initial_n;i++) {
        int tmp;
        scanf("%d",&tmp);
        add_num(tmp);
        add1(tong[tmp],1);
        if(tong[tmp]-1!=0)  add1(tong[tmp]-1,-1);
        add2(tong[tmp],tong[tmp]);
        if(tong[tmp]-1!=0)  add2(tong[tmp]-1,-tong[tmp]+1);
    }
    
    while(q--) {
        int p,k;
        scanf("%d%d",&p,&k);
        if(p==1) {
            add_num(k);
            n++; // 手动维护元素总数
            add1(tong[k],1);
            if(tong[k]-1 !=0 )  add1(tong[k]-1,-1);
            add2(tong[k],tong[k]);
            if(tong[k]-1 !=0 )  add2(tong[k]-1,-tong[k]+1);
        } else if(p==2) {
            if(tong[k] <=0) { // 修复：防御性判断
                printf("Error: Cannot delete %d\n",k);
                continue;
            }
            n--;
            tong[k]--;
            if(!tong[k]) num--;
            if(tong[k]) add1(tong[k],1);
            add1(tong[k]+1,-1);
            if(tong[k]) add2(tong[k],tong[k]);
            add2(tong[k]+1,-tong[k]-1);
        } else if(p==3) {
            printf("%lld\n",(n-ask2(k))-(num-ask1(k)));
        }
    }
    return 0;
}
 
 
 验证方法 
 
 测试正常添加/删除 ：确保基础功能正常。 
 测试删除不存在元素 ：输入 p=2 且 k 不存在时，应输出错误信息而非崩溃。 
 压力测试 ：用大数据量验证内存访问是否越界。 
 
 请根据上述修复后的代码重新编译运行，应该可以解决死机问题。

感谢大佬！！！

求大佬的洛谷用户名（关注一下）