一、差分标记介绍
差分标记用来解决针对区间(修改-查询)的问题，复杂度比线段树要更低。推荐这个博客。
例如，给数组中处于某个区间的数进行加减操作，然后查询某个位置上数的变化值。
二、HDU1556 Color the ball
2.1题意
N个气球依次编号为1,2,3....N.每次给定2个整数a b(a <= b),从气球a开始到气球b依次给每个气球涂一次颜色。求查询每个气球被涂的次数。
2.2分析
这里所有初始值为0，最后答案就是经过差分标记得到的变化值。
2.3代码
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
const int maxn = 1e5+;
int sum[maxn];
int N;
void Init()
{
memset(sum,,sizeof(sum));
}
void Solve()
{
int l,r;
for(int i=;i<N;i++)
{
scanf("%d%d",&l,&r);
sum[l]++;
sum[r+]--;
}
int res = ;
for(int i=;i<N;i++)
{
res += sum[i];
printf("%d ",res);
}
res += sum[N];
printf("%d\n",res);
}
int main()
{
while(scanf("%d",&N)!=EOF)
{
if(N==) break;
Init();
Solve();
}
return ;
}
三、牛客contest 135-I 区间(题面)
3.1题意
有一个n个元素的数组a，对a[L]-a[R]进行M次操作：将a[L]-a[R]内的元素都加上P，询问a[l]-a[r]内的元素之和
3.2分析
经过M次操作的元素值等于初始值加上变化值，所以用差分标记得到变化值最后输出时再与原始值相加即可。注意会爆int以及不要开多个大数组。
3.3代码
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
const int maxn = 1e6+;
int n,M;
int a[maxn],sum[maxn];
void Init()
{
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
memset(sum,,sizeof(sum));
}
void Solve()
{
int q,L,R,P,l,r;
for(int i=;i<M;i++)
{
scanf("%d%d%d%d",&q,&L,&R,&P);
if(q==)
{
sum[L] -= P;
sum[R+] += P;
}
else
{
sum[L] += P;
sum[R+] -= P;
}
}
scanf("%d%d",&l,&r);
long long ans = ;
long long res = ;
for(int i=;i<=r;i++)
{
res += sum[i];
if(i>=l) ans += res + a[i];
}
printf("%lld\n",ans);
}
int main()
{
while(scanf("%d%d",&n,&M)!=EOF)
{
Init();
Solve();
}
return ;
}