出错代码链接-个人

个人正确代码

@Skyjoy 的题解代码（仅修改了数组大小以通过更改后数据）

首先说一下数据过水的问题。

这一份是我个人的第一次AC（在数据已经扩大后）的代码

#include <bits/stdc++.h>
namespace ztd{
    using namespace std;
    #define reg register
    #define ms(a) memset(a,0,sizeof(a))
    #define endl '\n'
    typedef long long ll;
    typedef unsigned long long ull;
    typedef unsigned int uint;
    typedef double db;
    //basic I/O
    template<typename T> inline T read(T& t) {//fast read
        t=0;short f=1;char ch=getchar();double d = 0.1;
        while (ch<'0'||ch>'9') {if (ch=='-') f=-f;ch=getchar();}
        while (ch>='0'&&ch<='9') t=t*10+ch-'0',ch=getchar();
        if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
        t*=f;
        return t;
    }
}
using namespace ztd;
const int maxn = 1e6+7;
const ll inf = 11451419198101919;
#define int long long
int n, qq, a[maxn];
//区改单查 (t)， 存储修改的数组

int t[maxn];
int lowbit(int x){
	return x & -x;
}
void add1(int x, int k){
	while(x <= n){
		t[x] += k;
		x += lowbit(x);
	}
}
int sum1(int x){
    int ans = 0;
    while(x){
    	ans += t[x];
        x -= lowbit(x);
    }
    return ans;
}
inline void update1(int l, int r, int k){
	add1(l,k);
	add1(r+1,-k);
}
inline int query1(int x){
	return a[x] + sum1(x);
}

//单改区查 (delta)， 存储前后大小关系

int d[maxn];
void add2(int x, int k){
	while(x <= n){
		d[x] += k;
		x += lowbit(x);
	}
}
int sum2(int x){
    int ans = 0;
    while(x){
    	ans += d[x];
        x -= lowbit(x);
    }
    return ans;
} 
int query2(int l, int r){
	return sum2(r) - sum2(l-1);
}

signed main(){
	read(n); read(qq);
	a[0] = -inf;
	for(int i = 1; i <= n; ++i){
		read(a[i]);
		if(a[i] >= a[i-1]) add2(i,1);
	} 
	int opt, l, r, x, L1, L2, R1, R2, Lt, Rt;
	int cnt = 0;
	while(qq--){
		cnt ++;
		read(opt); read(l); read(r);
		if(l > r && opt == 2){
			puts("No");
			continue;
		}else if(l > r && opt == 1) continue;
		if(opt == 1){ //update
			read(x);
			update1(l,r,x);
			
           //如果大小关系在修改后变化，则更改记录大小关系的树状数组的记录
			if(l > 1){
				L1 = query1(l), L2 = query1(l-1); Lt = query2(l,l);
				if(L1 < L2 && Lt) add2(l,-1);
				else if(L1 > L2 && !Lt) add2(l,1);//错误
//				else if(L1 >= L2 && !Lt) add2(l,1);正确代码
			}
			
			if(r < n){
				R1 = query1(r+1), R2 = query1(r); Rt = query2(r+1,r+1);
				if(R1 < R2 && Rt) add2(r+1,-1);
				else if(R1 > R2 && !Rt) add2(r+1,1);//错误
//				else if(R1 >= R2 && !Rt) add2(r+1,1);正确代码
			}
				
		}else{//query
			if(l == r){
				puts("Yes");
				continue;
			}
			if(query2(l+1,r) == r-l) puts("Yes");
			else puts("No");
		}
	}
    return 0;
}

思路大致和排名第1的题解 @一只爬行者 的一样，由于在区间内一次更改不变化内部大小关系，所以每次只需要修改两次大小关系就可以。

很明显，在我标了 错误/正确 的地方，这个大于号应该取等，因为本质上题目中“先辈”的定义就是区间单调不降，所以说维护的大小状态应该分成 a[i+1] >= a[i]和a[i+1] < a[i]。所以在修改状态的时候也是要按这样改的。但很明显，在我错误的AC代码中，并没有在a[i+1] == a[i]的时候进行修改状态。所以说数据中压根没有卡两个相等的情况，甚至（有可能）不存在两个相等的情况。

抱着这个心理，我去试了一下几个题解。

数据

2 5
114514 1919810
2 1 2
1 2 2 -1919800
2 1 2
1 2 2 114504
2 1 2

由脑算，可知结果应为

Yes
No
Yes

然而, @loveJY @linaonao @Skyjoy 三位大佬的题解代码输出均为

Yes
Yes
Yes

是错误的。并且在题解上也没有声明代码有防作弊标记。我还测试了@Skyjoy 的题解代码，发现确实可以AC。