SP18185 GIVEAWAY - Give Away（单点修改）（纯纯的分块，享受纯粹的暴力快乐）（三倍经验） · znzryb
## 思路讲解
思路就是根号分治
```cpp
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的可以这么写。
```cpp
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](https://www.luogu.com.cn/record/220963190)
::: 源代码
```cpp
// 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](https://www.luogu.com.cn/record/220973015) 双倍经验，**SP3261 RACETIME - Race Against Time**
::: 源代码
```cpp
// 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](https://www.luogu.com.cn/record/220977711) 三倍经验，**UVA12003 Array Transformer**
::: 源代码
```cpp
// 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……）