题目列表

• P3374 【模板】树状数组 1
• P3368 【模板】树状数组 2
• P4939 Agent2
• P5057 [CQOI2006] 简单题
• P1908 逆序对
• P1774 最接近神的人
• P2068 统计和
• P3655 不成熟的梦想家 (未熟 DREAMER)

以下是正文部分

P3374 <单点修改、区间查询模版>

板子1

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
int a[maxn],n,m;
#define lowbit(x) (x&-x);
void updata(int x,int k){
	while(x<=n){
		a[x]+=k; 
		x+=lowbit(x);
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=a[x];
		x-=lowbit(x);
	}
	return ans;
}
int main() {
	cin>>n>>m;
	int x,y,z;
	for(int i=1;i<=n;i++){
		cin>>x;
		updata(i,x);
	}
	for(int i=1;i<=m;i++){
		cin>>z>>x>>y;
		if(z==1)updata(x,y);
		else cout<<(query(y)-query(x-1))<<"\n";
	}
	return 0;
}

P3368 <区间修改、单点查询模版>

板子2

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+5;
int a[maxn],b[maxn],n,m; 
inline int lowbit(int x){
	return x&-x;
}
void add(int i,int k){
	while(i<=n){
		a[i]+=k;
		i+=lowbit(i);
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=a[x];
		x-=lowbit(x);
	}
	return ans;
}
int main() {
	cin>>n>>m;
	int t,x,y,k;
	for(int i=1;i<=n;i++){
		cin>>b[i];
		add(i,b[i]-b[i-1]);
	}
	//cout<<a[1]<<"\n";
	for(int i=1;i<=m;i++){
		cin>>t>>x;
		if(t==1){
			cin>>y>>k;
			add(x,k);
			add(y+1,-k);
		}
		else cout<<query(x)<<"\n";
	}
	return 0;
}

P4939 Agent2<区间修改、单点查询>

这道题依旧很板子，与P3368很相似。也是区间修改、单点查询，每次修改的值为 $1$ ，使用差分维护即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
int a[maxn];
#define lowbit(x) (x&-x)
int n,m;
int query(int x){
	int ans=0;
	while(x>0){
		ans+=a[x];
		x-=lowbit(x);
	}
	return ans;
}
void add(int x,int k){
	while(x<=n){
		a[x]+=k;
		x+=lowbit(x);
	}
}
int main() {

	cin>>n>>m;
	int f,x,y;
	for(int i=1;i<=m;i++) {
		cin>>f;
		if(f){
			cin>>x;
			cout<<query(x)<<"\n";
		}else {
			cin>>x>>y;
			add(x,1);
			add(y+1,-1);
		}
	}
}

P5057 [CQOI2006] 简单题 <区间修改、单点查询>

注意到$1 \le m \le 5 \times 10^5$ , 数据范围很小，直接每次判断该点修改次数是奇数还是偶数即可。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7+5;
int a[maxn];
#define lowbit(x) (x&-x)
int n,m;
int query(int x){
	int ans=0;
	while(x>0){
		ans+=a[x];
		x-=lowbit(x);
	}
	return ans;
}
void add(int x,int k){
	while(x<=n){
		a[x]+=k;
		x+=lowbit(x);
	}
}
int main() {

	cin>>n>>m;
	int f,x,y;
	for(int i=1;i<=m;i++) {
		cin>>f;
		if(f==2){
			cin>>x;
			cout<<(query(x)%2==0?0:1)<<"\n";
		}else {
			cin>>x>>y;
			add(x,1);
			add(y+1,-1);
		}
	}
}

$\star$ P1908 逆序对 <离散化+单点修改、区间查询>

这题我就已经感到吃力并且不会做了。
大体思路就是从小到大遍历，每次使用树状数组维护当前非逆序对,也就是:

$$\sum_{j=1}^{a_i} {（大小=j的元素的个数）}$$

可以使用树状数组的前缀和计算。答案加上用本来的位置减去非逆序对的个数。
由于元素范围达到了 $10^9$ ，所以需要使用离散化处理。
另外：
$\large{不开long \ long 见祖宗}$

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&-x)
const int maxn = 5e5+5;
struct node{
	int num,i;
}a[maxn];
int t[maxn];
int n,m[maxn];
bool cmp(node a,node b){
	if(a.num==b.num)return a.i<b.i;
	return a.num<b.num;
}
inline void add(int x){
	while(x<=n){
		t[x]++;
		x+=lowbit(x);
	}
}
int query(int x){
	int ans=0;
	while(x){
		ans+=t[x];
		x-=lowbit(x);
	}
	return ans;
}
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].num;
		a[i].i=i;
	}
	long long ans=0;
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++)m[a[i].i]=i;
	for(int i=1;i<=n;i++){
		add(m[i]);
		ans+=i-query(m[i]);
	}
	cout<<ans;
	return 0;
}

P1774 最接近神的人 <逆序对>

和上面一个一样的，代码都不用改,就不放了。

$\star$P3655 不成熟的梦想家 (未熟 DREAMER)

这是一道好题目啊。虽然没能独立做出来
首先，魅力值的计算方式很像差分，并且一个数值只与前后两个有关。
而当修改时，区间内的差不会改变，但是两端的显然不会不变。只需要更新两个区间端点即可。
不过需要注意，当右端点下标等于 $n$ 时，不需要更新。不过如果没有判断，由于正常单点查询并计算差值时，结果会为 $0$ ，也就相当于没有更新，仍然可以AC。
还有就是如果想要去除本来的绝对值符号一定要注意判断正负。否则你连样例都过不了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e5+5;
ll a[maxn],b[maxn],n,m,s,t; 
inline ll lowbit(int x){
	return x&-x;
}
void add(ll i,ll k){
	while(i<=n){
		a[i]+=k;
		i+=lowbit(i);
	}
}
ll query(ll x){
	ll ans=0;
	while(x){
		ans+=a[x];
		x-=lowbit(x);
	}
	return ans;
}
inline ll f(ll x){
	return x>0?-s*x:-t*x;
}
int main() {
	cin>>n>>m>>s>>t;
	ll x,y,z,ans=0;
	cin>>b[0];
	for(int i=1;i<=n;i++){
		cin>>b[i];
		add(i,b[i]-b[i-1]);
		ans+=f(b[i]-b[i-1]);
	}
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		ans-=f(query(x)-query(x-1));
		/*if(y<n)*/ans-=f(query(y+1)-query(y));
		
		add(x,z);
		add(y+1,-z);
		
		ans+=f(query(x)-query(x-1));
		/*if(y<n)*/ans+=f(query(y+1)-query(y));
		
		cout<<ans<<"\n";
	}
	return 0;
}