SP18185 GIVEAWAY - Give Away（单点修改）（纯纯的分块，享受纯粹的暴力快乐）（三倍经验）

思路讲解

思路就是根号分治

FOR(_,1,Q){
	ll op,a,b,c;
	cin>>op;
	if(op==0){
		cin>>a>>b>>c;
		ll ida=upper_bound(L+1,L+1+idx,a)-L;
		ida-=1;
		ll idb=upper_bound(L+1,L+1+idx,b)-L;
		idb-=1;
		ll ans=0;
		FOR(i,0,SZ(g[ida])-1){
			if(g[ida][i][1]>=a && g[ida][i][1]<=b && g[ida][i][0]>=c){
				++ans;
			}
		}
		if(ida!=idb){    // 注意这个地方，小心相同重复统计导致WA
			FOR(i,0,SZ(g[idb])-1){
				if(g[idb][i][1]>=a && g[idb][i][1]<=b && g[idb][i][0]>=c){
					++ans;
				}
			}
		}
		FOR(i,ida+1,idb-1){
			ll id=lower_bound(all(g[i]),(arr2){c,0})-g[i].begin();
			ans+=SZ(g[i])-id;
		}
		cout<<ans<<"\n";
	}else{
		cin>>a>>b;
		ll id=upper_bound(L+1,L+1+idx,a)-L;
		id-=1;
		FOR(i,0,SZ(g[id])-1){
			if(g[id][i][1]==a){
				g[id][i][0]=b;
				break;
			}
		}
		sort(all(g[id]));
	}
}

如果问小于等于c的可以这么写。

FOR(i,ida+1,idb-1){
	ll id=upper_bound(all(g[i]),(arr2){c,INF})-g[i].begin();
	ans+=id;
}

AC代码

https://www.luogu.com.cn/record/220963190

源代码

// Problem: SP18185 GIVEAWAY - Give Away
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP18185
// Memory Limit: 1495 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
ll L[MAXN],R[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
inline void init(){
	
}

inline void solve(){
	cin>>N;
	init();
	ll sqn=sqrt(N),idx=1;
	L[idx]=1,R[idx]=sqn;
	FOR(i,1,N){
		ll a;
		cin>>a;
		if(i<=R[idx]){
			g[idx].pb({a,i});
		}else{
			++idx;
			L[idx]=i;
			R[idx]=i+sqn-1;
			g[idx].pb({a,i});
		}
	}
	FOR(i,1,idx) sort(all(g[i]));
	L[idx+1]=INF;
	cin>>Q;
	FOR(_,1,Q){
		ll op,a,b,c;
		cin>>op;
		if(op==0){
			cin>>a>>b>>c;
			ll ida=upper_bound(L+1,L+1+idx,a)-L;
			ida-=1;
			ll idb=upper_bound(L+1,L+1+idx,b)-L;
			idb-=1;
			ll ans=0;
			FOR(i,0,SZ(g[ida])-1){
				if(g[ida][i][1]>=a && g[ida][i][1]<=b && g[ida][i][0]>=c){
					++ans;
				}
			}
			if(ida!=idb){
				FOR(i,0,SZ(g[idb])-1){
					if(g[idb][i][1]>=a && g[idb][i][1]<=b && g[idb][i][0]>=c){
						++ans;
					}
				}
			}
			FOR(i,ida+1,idb-1){
				ll id=lower_bound(all(g[i]),(arr2){c,0})-g[i].begin();
				ans+=SZ(g[i])-id;
			}
			cout<<ans<<"\n";
		}else{
			cin>>a>>b;
			ll id=upper_bound(L+1,L+1+idx,a)-L;
			id-=1;
			FOR(i,0,SZ(g[id])-1){
				if(g[id][i][1]==a){
					g[id][i][0]=b;
					break;
				}
			}
			sort(all(g[id]));
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/220963190
*/

https://www.luogu.com.cn/record/220973015 双倍经验，SP3261 RACETIME - Race Against Time

源代码

// Problem: SP3261 RACETIME - Race Against Time
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/SP3261
// Memory Limit: 1495 MB
// Time Limit: 1240 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
ll L[MAXN],R[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
inline void init(){
	
}

inline void solve(){
	cin>>N>>Q;
	init();
	ll sqn=sqrt(N),idx=1;
	L[idx]=1,R[idx]=sqn;
	FOR(i,1,N){
		ll a;
		cin>>a;
		if(i<=R[idx]){
			g[idx].pb({a,i});
		}else{
			++idx;
			L[idx]=i;
			R[idx]=i+sqn-1;
			g[idx].pb({a,i});
		}
	}
	FOR(i,1,idx) sort(all(g[i]));
	L[idx+1]=INF;
	FOR(_,1,Q){
		char op;ll a,b,c;
		cin>>op;
		if(op=='C'){
			cin>>a>>b>>c;
			ll ida=upper_bound(L+1,L+1+idx,a)-L;
			ida-=1;
			ll idb=upper_bound(L+1,L+1+idx,b)-L;
			idb-=1;
			ll ans=0;
			FOR(i,0,SZ(g[ida])-1){
				if(g[ida][i][1]>=a && g[ida][i][1]<=b && g[ida][i][0]<=c){
					++ans;
				}
			}
			if(ida!=idb){
				FOR(i,0,SZ(g[idb])-1){
					if(g[idb][i][1]>=a && g[idb][i][1]<=b && g[idb][i][0]<=c){
						++ans;
					}
				}
			}
			FOR(i,ida+1,idb-1){
				ll id=upper_bound(all(g[i]),(arr2){c,INF})-g[i].begin();
				ans+=id;
			}
			cout<<ans<<"\n";
		}else{
			cin>>a>>b;
			ll id=upper_bound(L+1,L+1+idx,a)-L;
			id-=1;
			FOR(i,0,SZ(g[id])-1){
				if(g[id][i][1]==a){
					g[id][i][0]=b;
					break;
				}
			}
			sort(all(g[id]));
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/220973015
*/

https://www.luogu.com.cn/record/220977711 三倍经验，UVA12003 Array Transformer

源代码

// Problem: UVA12003 Array Transformer
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/UVA12003
// Memory Limit:  MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define lson(var) (var<<1)
#define rson(var) ((var<<1)+1)

using namespace std;

typedef long long ll;typedef unsigned long long ull;
typedef double DB;typedef long double LD;
typedef __int128 i128;typedef pair<DB,DB> pdd;typedef pair<ll,bool> plb;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr3;typedef array<ll,2> arr2;
constexpr ll MAXN=static_cast<ll>(1e6)+10,INF=static_cast<ll>(1e17)+9; // 1e18+9也是素数
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,Q,X,K,lT,A[MAXN];
/*

*/
ll L[MAXN],R[MAXN];
vector<arr2> g[MAXN];		// 记得要清空
inline void init(){
	
}

inline void solve(){
	ll u;
	cin>>N>>Q>>u;
	init();
	ll sqn=sqrt(N),idx=1;
	L[idx]=1,R[idx]=sqn;
	FOR(i,1,N){
		ll a;
		cin>>a;
		if(i<=R[idx]){
			g[idx].pb({a,i});
		}else{
			++idx;
			L[idx]=i;
			R[idx]=i+sqn-1;
			g[idx].pb({a,i});
		}
	}
	FOR(i,1,idx) sort(all(g[i]));
	L[idx+1]=INF;
// #ifdef LOCAL
    // debug(Q);
// #endif
	FOR(_,1,Q){
		ll p,a,b,c;
		cin>>a>>b>>c>>p;
		ll ida=upper_bound(L+1,L+1+idx,a)-L;
		ida-=1;
		ll idb=upper_bound(L+1,L+1+idx,b)-L;
		idb-=1;
		ll ans=0;
		FOR(i,0,SZ(g[ida])-1){
			if(g[ida][i][1]>=a && g[ida][i][1]<=b && g[ida][i][0]<c){
				++ans;
			}
		}
		if(ida!=idb){
			FOR(i,0,SZ(g[idb])-1){
				if(g[idb][i][1]>=a && g[idb][i][1]<=b && g[idb][i][0]<c){
					++ans;
				}
			}
		}
		FOR(i,ida+1,idb-1){
			// 严格小于c
			ll id=lower_bound(all(g[i]),(arr2){c-1,INF})-g[i].begin();
			ans+=id;
		}
		// 修改部分
		ll id=upper_bound(L+1,L+1+idx,p)-L;
		id-=1;
		FOR(i,0,SZ(g[id])-1){
			if(g[id][i][1]==p){
				g[id][i][0]=u*ans/(b-a+1);
				break;
			}
		}
		sort(all(g[id]));
	}
	FOR(i,1,idx){
		sort(all(g[i]),[](const arr2 &a,const arr2 &b){return a[1]<b[1];});
		// FOR(j,0,SZ(g[i])-1){
			// if(j==SZ(g[i])-1 && i==idx) {cout<<g[i][j][0];}
			// else {cout<<g[i][j][0]<<"\n";}
		// }
		FOR(j,0,SZ(g[i])-1){
			cout<<g[i][j][0]<<"\n";
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	// cin>>lT;
	// while(lT--){
		// solve();
	// }
	solve();
	return 0;
}
/*
AC
https://www.luogu.com.cn/record/220977711
*/

心路历程（WA，TLE，MLE……）