题意
给定一个平面\((n,m)\)，处理如下操作：
- OPT = 1：使点\((x,y)\)处使横纵行全部0/1取反。
- OPT = 2：矩形\((x_1,y_1,x_2,y_2)\)内的和。
给定一个平面\((n,m)\)，处理如下操作：
给一个排列\(p[1-n]\)和取值范围在\([1,n]\)内的数组\(a[]\)，处理\(q\)个询问：在数组的字段\([l,r]\)内是否存在排列的环形偏移。
考虑正向扫描，处理出每一个位置上的数到左边「最近的上一个环形偏移数」的位置，并同时更新自己所在的位置供下一次循环进行使用：
这道题的主要做法就是贪心了。我们枚举\(i\)从\(n-1\)到\(1\)，记\(vis[i]\)为编号为\(i\)的节点是否可以转移、\(arr[i]\)为\(i\)位置上的数，在转移关系集中寻找\((i,j), vis[j]=true\)的\(j\)。由于我们是从后向前转移，所以我们找到的这些\(j\)的位置都是在\(i\)之后的，符合转移要求。之后我们验证目前已转移的答案\(ans\)与满足条件的关系个数\(cnt\)与\(i\)的和是否为\(n\)，如果符合意味着转移符合条件，便直接进行转移；如果不符合，那么我们把该点的标记打上，意味着可以从此被转移。
很简单，扫描的时候如果所在数位为偶数位，向答案添加当前数位即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
char str[66000];
int main()
{
int ans = 0, len;
scanf("%d", &len), scanf("%s", str + 1);
for (int i = 1; i <= len; i++)
if (((str[i] - '0') & 1) == 0)
ans += i;
printf("%d", ans);
return 0;
}
我们先来考虑无限制的版本，也就是不考虑询问的硬币数量限制。我们可以用一个完全背包搞一搞，复杂度为线性。
dp[0] = 1;
for (int i = 0; i < 4; i++)
for (int j = ci[i]; j < MAX_N; j++)
dp[j] += dp[j - ci[i]];
学习树上差分的前提是：
学习了这些之后，我们就可以开始学习树上差分了。树上差分的思想跟差分类似：都是在不得不求前缀和的情况下，将区间操作变为单点操作，降低复杂度。树上差分曾两次在 NOIp 系列比赛中出现过，所以学习树上差分很有必要（我怀疑是出题组不敢出树链剖分，但又要考察选手们对树上操作的熟悉程度，所以采用了这么个坑爹玩意）。我们先来学习一个基本的操作：点的链上区间加。