—— Summon, Light!

A - 求递推序列的第N项

矩阵快速幂，帮助大家搭建/测试自己的模板。
简单地讲一下原理，可以看到每一项用到了前两项的值，首先构造一个二维的向量$\left(\begin{matrix}
f(i-1) \\
f(i-2) \\
\end{matrix}\right)$，如果有常数就再加一维。那么将这个向量作为自变量，下一项就是$\left(\begin{matrix}
f(i) \\
f(i-1) \\
\end{matrix}\right)$。最后稍微动一下脑子配一个$2\times2$的系数矩阵使得$Cx_{i-1}=x_{i}$：
$$\left(\begin{matrix}
A & B \\
1 & 0 \\
\end{matrix}\right)
\left(\begin{matrix}
f(i-1) \\
f(i-2) \\
\end{matrix}\right)
=\left(\begin{matrix}
f(i) \\
f(i-1) \\
\end{matrix}\right)$$
复杂度$O(M^3logN)$，其中$M$为矩阵的大小，等于$2$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MO=7;

struct Matrix {
    int r,c;
    ll e[2][2];
    Matrix() {}
    Matrix(int _r,int _c) {
        r=_r;c=_c;
        memset(e,0,sizeof(e));
    }
    Matrix(ll x) {
        r=c=2;
        memset(e,0,sizeof(e));
        for (int i=0;i<r;i++) {
            e[i][i]=x;
        }
    }
    Matrix operator *(const Matrix &b) {
        Matrix C(r,b.c);
        for (int i=0;i<r;i++) {
            for (int j=0;j<b.c;j++) {
                for (int k=0;k<c;k++) {
                    C.e[i][j]+=e[i][k]*b.e[k][j]%MO;
                    if (C.e[i][j]>=MO) C.e[i][j]%=MO;
                }
            }
        }
        return C;
    }
};

Matrix fpow(Matrix x,ll n)
{
    Matrix res(1);
    while (n) {
        if (n&1) {
            res=res*x;
        }
        x=x*x;
        n>>=1;
    }
    return res;
}

int main()
{
    int a,b,n;
    scanf("%d%d%d",&a,&b,&n);
    if (n<=2) {
        puts("1");
    } else {
        Matrix A(2,2);
        A.e[0][0]=a;
        A.e[0][1]=b;
        A.e[1][0]=1;
        A.e[1][1]=0;
        Matrix X(2,1);
        X.e[0][0]=1;
        X.e[1][0]=1;
        A=fpow(A,n-2);
        X=A*X;
        int ans=(X.e[0][0]%MO+MO)%MO;
        printf("%d\n",ans);
    }
    return 0;
}

B - Kinds of Fuwas

题意：四个角为同一种福娃的子矩形有多少个？
题解：从样例可以看出，一行或一列的矩形都不算。从数据范围来看，直接四个循环复杂度太高了，但是每个元素的值域很小，只有五个种类，所以可以考虑枚举每个种类来做。对于每个种类，比如H，我们可以利用类似最大子矩阵的套路，枚举两行作为上下界，然后再枚举每一列，对上下都是H的列进行计数，在这之中任取两列就是符合要求的矩形，所以把答案加上$C^{2}_{m}$即可，这个组合数可以$O(1)$求得。
复杂度$(KM^2N)$，其中$K$等于$5$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <bits/stdc++.h>
using namespace std;

const char PP[9]="BJHYN";
const int N=256;
char mp[N][N];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++) {
            scanf("%s",mp[i]);
        }
        long long ans=0;
        for (int p=0;p<5;p++) {
            for (int i=0;i<n;i++) {
                for (int j=i+1;j<n;j++) {
                    int t=0;
                    for (int k=0;k<m;k++) {
                        if (mp[i][k]==PP[p]&&mp[j][k]==PP[p]) ++t;
                    }
                    ans+=t*(t-1)/2;
                }
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C - GCD is Funny

题意：
在黑板上写有$n$个数，每次删掉$a,b,c$三个数并把$d$写两遍，$d$可以是$(a,b),(a,c),(b,c)$。在$n-2$次操作后会留下两个相同的数，输出这个数的所有可能情况。

题解：
这个题很难虽然出在某一场BC的A题。
首先要思考一下脱离具体过程，这个数到底是什么。题中的过程以下简称为“擦黑板”。

1. 如果已经存在两个相同的数$x$，再取一个数$y$进行一次擦黑板，那么可以令$d=(x,x)=x$，剩下的数为$x,x$。可以发现$y$没有产生影响，两个$x$直接“吃掉”了$y$；
2. 由1，我们可以单独考虑每一个$size\ge 3$的子集，它的结果一定是两个相同的数，其他的数直接吃掉就好。为了保证枚举的不重不漏，该子集内应该有尽量多的数参与$gcd$运算（注意，参与擦黑板$\neq$参与$gcd$运算），也就是$size-1$个数。因为第一次擦黑板一定有一个数无法参与$gcd$运算，而从第二次开始，有前一次得到的两个数$x$，再取一个数$y$进行一次擦黑板，那么可以令$d=(x,y)$，$y$一定能参与$gcd$运算。

以下全文转载自：C语言函数调用栈（一）

程序的执行过程可看作连续的函数调用。当一个函数执行完毕时，程序要回到调用指令的下一条指令（紧接call指令）处继续执行。函数调用过程通常使用堆栈实现，每个用户态进程对应一个调用栈结构（call stack）。编译器使用堆栈传递函数参数、保存返回地址、临时保存寄存器原有值（即函数调用的上下文）以备恢复以及存储本地局部变量。

不同处理器和编译器的堆栈布局、函数调用方法都可能不同，但堆栈的基本概念是一样的。

1 寄存器分配

寄存器是处理器加工数据或运行程序的重要载体，用于存放程序执行中用到的数据和指令。因此函数调用栈的实现与处理器寄存器组密切相关。

Intel 32位体系结构（简称IA32）处理器包含8个四字节寄存器，如下图所示：

最初的8086中寄存器是16位，每个都有特殊用途，寄存器名城反映其不同用途。由于IA32平台采用平面寻址模式，对特殊寄存器的需求大大降低，但由于历史原因，这些寄存器名称被保留下来。在大多数情况下，上图所示的前6个寄存器均可作为通用寄存器使用。某些指令可能以固定的寄存器作为源寄存器或目的寄存器，如一些特殊的算术操作指令imull/mull/cltd/idivl/divl要求一个参数必须在%eax中，其运算结果存放在%edx（高32位）和%eax （低32位）中；又如函数返回值通常保存在%eax中，等等。为避免兼容性问题，ABI规范对这组通用寄存器的具体作用加以定义（如图中所示）。

对于寄存器%eax、%ebx、%ecx和%edx，各自可作为两个独立的16位寄存器使用，而低16位寄存器还可继续分为两个独立的8位寄存器使用。编译器会根据操作数大小选择合适的寄存器来生成汇编代码。在汇编语言层面，这组通用寄存器以%e（AT&T语法）或直接以e（Intel语法）开头来引用，例如mov $5, %eax或mov eax, 5表示将立即数5赋值给寄存器%eax。

在x86处理器中，EIP（Instruction Pointer）是指令寄存器，指向处理器下条等待执行的指令地址（代码段内的偏移量），每次执行完相应汇编指令EIP值就会增加。ESP（Stack Pointer）是堆栈指针寄存器，存放执行函数对应栈帧的栈顶地址（也是系统栈的顶部），且始终指向栈顶；EBP（Base Pointer）是栈帧基址指针寄存器，存放执行函数对应栈帧的栈底地址，用于C运行库访问栈中的局部变量和参数。

注意，EIP是个特殊寄存器，不能像访问通用寄存器那样访问它，即找不到可用来寻址EIP并对其进行读写的操作码（OpCode）。EIP可被jmp、call和ret等指令隐含地改变（事实上它一直都在改变）。

C-平分游戏

先不考虑是隔$k$个人，直接当成每次逆时针加$k$。那么原图中的$n$个人划分为若干个环，每个环都是独立的，这里取一个四元环继续讲解。

假设四个人原先有的钱为$S_i$，逆时针收到的钱为$x_i$（负数即反向），需要达到平均值$A$，那么有
$$
\left\{
\begin{array}{c}
S_1+x_1-x_2=A \\
S_2+x_2-x_3=A \\
S_3+x_3-x_4=A \\
S_4+x_4-x_1=A
\end{array}
\right.
$$
一行一行加，解得：
$$
\left\{
\begin{array}{c}
x_1=&x_1 &\triangleq x_1-y_1 \\
x_2=&x_1-(A-S_1) &\triangleq x_1-y_2 \\
x_3=&x_1-((A-S_1)+(A-S_2)) &\triangleq x_1-y_3 \\
x_4=&x_1-((A-S_1)+(A-S_2)+(A-S_3)) &\triangleq x_1-y_4
\end{array}
\right.
$$
这个环所需要的总时间为$T=|x_1|+|x_2|$ $+|x_3|+|x_4|$ $=|x_1-y_1|+|x_1-y_2|$ $+|x_1-y_3|+|x_1-y_4|$，由绝对值数形结合的知识可知当$x_1$取$y_i$的中位数（不计平均）时该式最小。
对于这道题，可以先求出总的平均值$A$，然后每个环都用这个$A$列方程和验证，答案累加即可。
最后说一下$k$的问题，题意不是很清晰，最终确定隔$n-1$个人是可以的（相当于相邻），隔$n$个人是不可以的（没有实际意义）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=1000010;
ll s[N];
bool vis[N];

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    ++k;
    ll sum=0;
    for (int i=0;i<n;i++) {
        scanf("%lld",&s[i]);
        sum+=s[i];
    }
    if (sum%n) {
        puts("gg");
        return 0;
    }
    ll A=sum/n,ans=0;
    int cnt=0;
    for (int i=0;i<n;i++) {
        cnt+=(s[i]==A);
    }
    if (cnt==n) {
        puts("0");
        return 0;
    }
    if (k>n) {
        puts("gg");
        return 0;
    }
    bool good=true;
    for (int i=0;i<n;i++) {
        if (vis[i]) continue;
        int j=i;
        ll tmp=0;
        vector<ll> ve;
        do {
            vis[j]=true;
            tmp+=A-s[j];
            ve.push_back(tmp);
            j=(j+k)%n;
        } while (j!=i);
        if (tmp) {
            good=false;
            break;
        }
        sort(begin(ve),end(ve));
        ll x=ve[ve.size()/2];
        for (auto y:ve) {
            ans+=abs(x-y);
        }
    }
    if (!good) {
        puts("gg");
    } else {
        printf("%lld\n",ans);
    }
    return 0;
}

F - 数塔

经典问题，数塔。
使用动态规划解决问题的（最重要）前提是：

1. 问题具有最优子结构
2. 最优子结构的状态可以记录

例如上图中，以第二层$12$为顶层的数塔就是一个最优子结构。
再回到原来的顶层，想得到最终的结果只需要知道第二层两个子结构能得到的最大和，这是可记录的。
所以，我们从底层往顶层进行动态规划就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#include <bits/stdc++.h>
using namespace std;

int a[111][111];

int main()
{
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=i;j++) {
                scanf("%d",&a[i][j]);
            }
        }
        for (int i=n-1;i>=1;i--) {
            for (int j=1;j<=i;j++) {
                a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
            }
        }
        printf("%d\n",a[1][1]);
    }
    return 0;
}

G - 免费馅饼

可以发现时刻的范围不是很大，把每个时刻看作每一层，这个问题就是三条边的数塔。
代码中平移一下是为了避免越界问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int dp[N][13];

int main()
{
    int n;
    while (scanf("%d",&n),n) {
        memset(dp,0,sizeof(dp));
        int m=0;
        for (int i=1;i<=n;i++) {
            int x,t;
            scanf("%d%d",&x,&t);
            ++dp[t][x+1];
            m=max(m,t);
        }
        for (int i=m;i>=0;i--) {
            for (int j=1;j<=11;j++) {
                dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]);
            }
        }
        printf("%d\n",dp[0][6]);
    }
    return 0;
}

A - 饭卡

首先排除余额已经少于$5$的情况，然后分为$m-5$和$5$两部分，前面的$m-5$是个01背包问题，后面的$5$用来买最后一次。若用$dp(x)$表示$x$能买到的最大价值，那么答案为$m-dp(m-5)-a_i (1\le i\le n)$。
可以证明，最后买最贵的是最优的。比较复杂，这里仅通过$m-dp(m-5)-a_p$这个式子简要说明，如果最后买的不是最贵的，即 $p’ \neq p$：

Before

听说考得好写在简历里很不错，准备参加三月份的CSP。
仅含题解，代码详见github。喜欢的话点个star

201712-1 最小差值

sb-t。随便暴力一下。

201712-2 游戏

sb-t。**BUT，**读题的时候没读到或其末位数（即数的个位）为k，直接当约瑟夫做了。。。
最垃圾的做法就是拿数组标记一下，手动控制环。（没错我就是这么做的，写起来还是很快的

201712-3 Crontab

还没读完题头都大了，写完第4题的第一稿才开始动手做。题目虽然很长，题意其实还是挺清晰的。
核心算法就是模拟，用了一次蔡勒公式算出星期几。输入处理简单来讲的话就是，先按‘ ’（空格）split，每段再按‘,’（逗号）split，每段再按‘-’（减号）split，然后再转换成非负整数标记到这个$crontab$对应的布尔数组，比如周一周二那就是在一周的数组中标记$1$和$2$，详见代码。最后从起始到终止一分钟一分钟往上加，每一分钟都枚举$n$个$crontab$判断一下是否满足。算了一下极限复杂度稍微有点方，不过看了一下输出不超过10000行，应该不会TLE。
思考加打代码估计有一个多小时。。。最后交上去一看，85分，难道还是TLE了？结果点进去一看是WA，有点懵逼。又读了一遍题，还是没啥发现。查了查别人代码发现好像英文缩写不区分大小写，然后回到题目里一看，中间有一句确实写着，唉。。。

201712-4 行车路线

ps. 201712-4.cpp是60分代码，201712-4S.cpp是满分代码。
其实核心思想跟之前是差不多的。首先因为小道的费用（和的平方）没有可加性，所以就要把小道全都做成$tp$（传送卷轴）：启动$tp$以后可以花费一定的费用从一个点传送到另一个点。其次为了保证小道的费用不可加，要限制$tp$不能连续使用，连续使用时费用缩水（$1^2+1^2<(1+1)^2$）。
具体实现是：首先用$Floyd$求出只用小道的任意点对间的距离，把这些距离的平方作为$tp$的费用存下来。然后用$SPFA$求单源最短路，分别用两个数组记录$tp$过来的（$dis1$）和从大道过来的（$dis0$），对于边$u\rightarrow v$，$tp$到$u$的不能再通过$tp$到$v$，其它的不作限制。最后输出$min(dis0(n),dis1(n))$即可。
ps. $Floyd+SPFA$有风险，一点不考虑常数优化的话交上去只有50分，比$dijkstra$乱搞还低。

正文

BEFORE

我校网赛打出来一个名额，教练钦定我们队去。
现在都是固定队了，我的队友是文文和老张。

自从听说浙大出题以后，我就一直努力想把zimpha出过的bestcoder都过一遍。
【虽然他不出这场但是我感觉题目风格可能有传承？咸鱼的挣扎 ←_←
结果发现他出过的bc题实在是太多了。。。于是就按照vj的规格拉了最近的26题练了练。。。非常重视思维，怎么说呢，感觉上没什么套路题，详见zimpha的bc出题录。

Oct 26

翻了翻高中通讯录，有一个东秦的同学，非常高兴地问她借了词典~
晚上让队友把这个简要题解也都过一遍，然后买了泡面和小香肠啥的第二天吃。

Oct 27

没有老师带队，我们自己坐高铁去，睡睡觉吃吃面看看片，日子过得还是挺开心的。路上感觉河北的污染确实比较严重，然后在高铁上问AA姐姐要了几个口罩2333333
下了高铁坐公交，跟wc一路。找到宾馆直接从人家后厨就进去了。。。还好找到了报到的地方，真的发了环卫工人服，一切正常。
安顿了一下就是饭点了，出去吃了个酱骨自助，竟然有个烧烤和小锅一体的机器！长见识。
吃了很久，筒骨还是蛮油的，差点肉醉[笑cry]
很饱的我们于是就想散个步，强行在老虎石公园拍了很多照片【基本看不清啥
逛完了出来看到卖手链的，问了问看了看，然后每个人买了个指尖陀螺？？？

Oct 28

早上吃饭，宾馆的实在是没啥想吃的东西，咖啡也不给喝。。。
坐主办方的车过去，结果报过到的队啥都不用干。。。
然后我们就开始瞎逛，不抱希望地联系了一下同学【因为她说周六早上没空
结果我们还没正式开始逛她就回复我啦，而且一下子就找到了我们~
她说是参加高数竞赛，然后水了水就出来了hhhhhhh

A - GCD is Funny

题意：在黑板上写有$n$个数，每次删掉$a,b,c$三个数并把$d$写两遍，$d$可以是$(a,b),(a,c),(b,c)$。在$n-2$次操作后会留下两个相同的数，输出这个数的所有可能情况。
题解：给跪了。。。其实是所有大小超过$1$的子集的$gcd$的集合。。。

注意点：值域限制，说是子集当然不可能直接按子集做，而是利用值域很小这一点标记着做；gcd下降速度，两个不一样的数取$gcd$，最大也只能是大数的一半，即对数级别次就可以到$1$。

B - Square Distance

题意：给一个串$s$，长度为$n$(保证偶数)，输出一个串$t$，要满足：$t$由两个相同的串拼接而成；$s$到$t$的汉明距离恰好为$m$；$t$是所有满足条件的串中字典序最小的。$s,t$均只含小写字母，若$t$不存在输出Impossible。
题解：后半段放到前半段综合考虑，用dp可以求出前$i$个字符产生$j$个距离可不可行。因为要输出字典序最小，所以最终的贪心一定是从前往后从小往大，若是直接在这种dp上贪心，会导致最后的距离不一定是$m$。所以这里需要倒着dp，即从第$\frac{n}{2}$个到第$i$个字符产生$j$个距离可不可行。

注意点：看着很像贪心但是没有具体策略的时候一定要想一想dp！不一定只贪心或者只dp，也不一定是用贪心优化dp，像这题就是在dp得到的表上进行贪心。

C - LCIS

题意：给出$n$个数的序列$a$和$m$个数的序列$b$，问公共的上升的并且数值连续的子序列的最长长度。
题解：对$a$扫一遍得到以$x$结尾的连续值上升子序列的最长长度，同样地对$b$扫一遍，最后枚举结尾是什么数字，取两个结果的较小值更新答案。

注意点：当对子序列的限制非常强时，很有可能可以每个序列分开做，最后再合并到答案。

D - Black White Tree

Tips

仅含题解，代码详见github。喜欢的话点个star

A. Banana

直接暴力。

B. Out-out-control cars

可以看作相对运动，然后三条射线跟三条线段判相交。
要注意的是大三角形的射线不碰到小三角形也可以yes，这个我们可以通过两个都判一遍来解决。
还有一种情况（数据里好像没有）是两者相对静止并且一个套一个，按照题意也是yes。

C. Coconut

直接模拟。

D. Hack Portals

poj原题。没做过，所以比赛的时候也没做
按照坐标排序后，有一个贪心的结论：i到j这一段区间中，最优情况下最后一个做的不是i就是j。
考虑区间dp，我们用dp[i][j][0]表示i到j这一段最后做i的最小花费，dp[i][j][1]表示i到j这一段最后做j的最小花费。
转移还是挺容易的，转移了以后还要再考虑一下开放的时间。

以下全文转载自hihocoder，今天看了一遍突然就懂了，难道我以前看的都是假文章？
小Hi：今天我们来学习一个强大的字符串处理工具：后缀自动机（Suffix Automaton，简称SAM）。对于一个字符串S，它对应的后缀自动机是一个最小的确定有限状态自动机（DFA），接受且只接受S的后缀。

小Hi：比如对于字符串S=“aabbabd”，它的后缀自动机是：

其中红色状态是终结状态。你可以发现对于S的后缀，我们都可以从S出发沿着字符标示的路径（蓝色实线）转移，最终到达终结状态。例如"bd"对应的路径是S59，"abd"对应的路径是S189，"abbabd"对应的路径是S184679。而对于不是S后缀的字符串，你会发现从S出发，最后会到达非终结状态或者“无路可走”。**特别的，对于S的子串，最终会到达一个合法状态。**例如"abba"路径是S1846，"bbab"路径是S5467。**而对于其他不是S子串的字符串，最终会“无路可走”。**例如"aba"对应S18X，"aaba"对应S123X。（X表示没有转移匹配该字符）

小Ho：好像很厉害的样子！对于任意字符串都能构造出一个SAM吗？另外图中那些绿色虚线是什么？

小Hi：是的，任意字符串都能构造出一个SAM。我们知道SAM本质上是一个DFA，DFA可以用一个五元组**<字符集，状态集，转移函数、起始状态、终结状态集>来表示。下面我们将依次介绍对于一个给定的字符串S如何确定它对应的状态集和转移函数**。至于那些绿色虚线虽然不是DFA的一部分，却是SAM的重要部分，有了这些链接SAM是如虎添翼，我们后面再细讲。

SAM的States

小Hi：这一节我们将介绍给定一个字符串S，如何确定S对应的SAM有哪些状态。首先我们先介绍一个概念子串的结束位置集合endpos。对于S的一个子串s，endpos(s) = s在S中所有出现的结束位置集合。还是以S="aabbabd"为例，endpos(“ab”) = {3, 6}，因为"ab"一共出现了2次，结束位置分别是3和6。同理endpos(“a”) = {1, 2, 5}, endpos(“abba”) = {5}。

小Hi：我们把S的所有子串的endpos都求出来。如果两个子串的endpos相等，就把这两个子串归为一类。最终这些endpos的等价类就构成的SAM的状态集合。例如对于S=“aabbabd”：

小Ho：这些状态恰好就是上面SAM图中的状态。

小Hi：没错。此外，这些状态还有一些美妙的性质，且等我一一道来。首先对于S的两个子串s1和s2，不妨设length(s1) <= length(s2)，那么s1是s2的后缀当且仅当endpos(s1) ⊇ endpos(s2)，s1不是s2的后缀当且仅当endpos(s1) ∩ endpos(s2) = ∅。

Tips

仅含题解，代码详见github。喜欢的话点个star

1002. Ch’s gift

首先考虑序列上的问题。

$a$ 是一个二维数组，如果第 $i$ 位置的值为 $j$，就在 $a_{i,j}$上加上 $j$ 。那么某个询问 $x,y,a,b$ 的答案就是子矩阵的和。如果一开始就把二维前缀和算出来的话就可以回答$O(1)$，答案等于 $(Sum(y,b)-Sum(y,a-1))-(Sum(x,b)-Sum(x,a-1))$ 。

考虑到 $a,b$ 的范围非常大，可以把所有询问离散化。当然就算离散化，预处理二维前缀和还是不行的，我们发现前缀和相当于把 $[a,b]$ 拆成 $[1,b]-[1,a-1]$，联想到扫描线，把 $a,b$ 这一维的每个区间拆成两条线，用扫描线从小到大扫这一维，$x,y$ 这一维直接预处理一下前缀和每次 $O(1)$ 查就行了。

再搬到树上，直接套一个树链剖分就行了，树状数组就能维护。

ps: 可持久化线段树可以在线回答，等写出来了更新

1005. FFF at Valentine

强连通缩点加拓扑序判分叉，不多说了。