《D - Range Add Query》
题目大意：
给定一个长度为n的序列s，和一个整数k
我们可以对s进行无数次如下操作：
1、选定s中的一个下标i（1<=i<=n-k+1）
2. 对
这k个元素进行+c操作，c是个整数
如果能够将s的元素全部变成0,那么我们称s是一个好序列
现在给定一个长度为N的序列S，询问q次
每次询问给定区间：[l,r]
问这个区间的序列是否为好序列
解决思路：
毫无头绪，既然是区间+操作，
那么先从差分来试试：
差分，将区间+操作变成了对 差分数组 的两点操作
即对ca[l]+=c,那么对ca[r+1]-=c
最终原序列S【l,r】的数全部为0
则最终差分数组 ca[l+1,r]的数全部为0，且ca[l]=-S[l-1]
(为何？自己手写一个例子就明白了)
那么这个问题就变成了:
给定区间[l,r]
对差分数组ca可以进行无数次如下操作：
ca[i]+=c,ca[i+k]-=c (l<=i<=r-k+1)
问是否最终可以使得
差分数组ca[l+1,r]中的数全部为0
ca[l]=-S[l-1]
还是经过大量的手写模拟数据发现：
我们可以对下标%k
设sum[i]为在差分数组[l,r]上j%k==i的ca[j]之和
对于一般情况如果sum[i]==0,
那么就可以通过上面操作使得
如果sum[l]==-S[l-1]
那么就可以使得
还有一种特殊情况：
对于sum[(r+1)%k]是没有条件的，其为任意值都可以
为啥？
因为如：
1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 3 0 0
假设最后ca区间上为上面的序列，k=3
还可以对ca[7]-=3,ca[10]+=3
但是下标10已经不在区间要求的范围内 可以不管
上面的做法有点麻烦，如果已经领悟到下标%k的想法后
可以回到原序列S进行思考：
sum[i]=S下标j%k==i中，S[j]的和
选定i 对
的数+c
其实就是对
sum[0~k-1]进行+c操作
如果区间【l,r】全部为0
那么这个区间中的sum[0~k-1]也必然全部为0
如果这个区间中的sum[0~k-1]全部为0，
区间【l,r】也会全部为0吗？
会（不妨利用手写数据模拟一下，可以感性地证明出来）
这样其实就是看一下
S序列[l,r]中sum[0~k-1]中的数是否都相等
如果都相等，那么可以减去这个相等的数，那么sum[0~k-1]也都是为0了
如果不相等，那么这个【l,r】序列不是好序列
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<vector<int>> a(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; i++)
{
int num;
scanf("%d", &num);
for (int j = 0; j < k; j++)
{
if (i % k == j)
a[i][j] = a[i - 1][j] + num;
else
a[i][j] = a[i - 1][j];
}
}
int q;
cin >> q;
while (q--)
{
int l, r;
cin >> l >> r;
bool flag = false;
int same = a[r][0] - a[l - 1][0];
for (int i = 1; i < k; i++)
{
if (same != (a[r][i] - a[l - 1][i]))
{
flag = true;
break;
}
}
if (flag)
{
cout << "No" << endl;
}
else
cout << "Yes" << endl;
}
return 0;
}
标签：AtCoder,Beginner,int,ca,区间,差分,288,序列,sum From： https://www.cnblogs.com/cilinmengye/p/17099826.html