【题目描述】
\(1s,256MB\)
在一个平面直角坐标系中，有一个人偶，你可以控制它前进。有四种命令可以控制。设当前人偶所在的位置为 \((x,y)\) ：
- \(N\) ：向北移动一个单位，\((x,y)->(x,y+1)\)
- \(S\) ：向南移动一个单位，\((x,y)->(x,y-1)\)
- \(W\) ：向西移动一个单位，\((x,y)->(x-1,y)\)
- \(E\) ：向东移动一个单位，\((x,y)->(x+1,y)\)
现在，给定一个四种命令组成的字符串，人偶会自动按顺序执行字符串的每一个命令。若执行完毕，它又会从头开始执行命令，如此重复。
每一秒执行一个命令。若初始时人偶在 \((0,0)\) ，问 \(T\) 秒后人偶的位置。
【输入格式】
第一个行一个字符串 \(S\) ，表示给定的命令。
第二行一个整数 \(T\) ，表示时间。
【输出格式】
两个数 \(x,y\) ，表示最终的位置。
【样例输入】
NSWENSNEN 13
【样例输出】
1 2
【数据范围】
对于 \(60\%\) 的数据， \(T\le 5\times 10^5\) 。
对于 \(100\%\) 的数据，\(T\le 2\times 10^9，|S|\le 5000\) ，\(|S|\) 表示字符串长度。
【问题分析】
\(60\) 分：
按照每一秒的命令，模拟整个过程。时间复杂度为 \(O(T)\) 。
\(100\) 分：
每执行完一次字符串命令，人偶的横纵坐标的增加是固定的，若执行完一次字符串命令，从 \((0,0)—>(x,y)\) 。若再执行一次，位置变为 \((2x,2y)\) 。因此计算出执行完一次字符串命令横纵坐标的编号量，最多执行 \(\frac T {|S|}\) 次，剩下不足一次的就单独模拟。时间复杂度为 \(O(|S|)\) 。
【题目描述】
\(1s,256MB\)
给定一个 \(n\times m\) 的矩阵。计算子矩阵内的最大值并求和。小 \(F\) 完成的程序，准备提交了，但是他不会算时间复杂度，于是他写了一个这样的代码来计算：
#include<cstdio> using namespace std; int main(){ int n,m,i,j,k,l,x,y,tmp=0; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=m;j++) for(k=i;k<=n;k++) for(l=j;l<=m;l++) for(x=i;x<=k;x++) for(y=j;y<=l;y++) ++tmp; printf("%d\n",tmp); }这个程序所输出的
tmp就是他最初的程序的时间复杂度。现在，给定 \(n,m\)，计算出tmp。
【输入格式】
一行两个整数 \(n,m\) 。
【输出格式】
一个正整数 \(tmp\) ，数值可能会很大，将其模 \(10^9+7\) 后输出。
【样例输入】
5 5
【样例输出】
1225
【数据范围】
对于 \(20\%\) 的数据，满足 \(n,m\le 40\) 。
对于 \(40\%\) 的数据，满足 \(n,m\le 150\) 。
对于 \(60\%\) 的数据，满足 \(n,m\le 3000\) 。
对于 \(80\%\) 的数据，满足 \(n,m\le 10^7\) 。
对于 \(100\%\) 的数据，满足 \(1\le n,m\le 10^{18}\) 。
【问题分析】
\(60\) 分：
若固定了矩阵的左上角 \((i,j)\) ，就可以统计出计算次数。
对于 \(N\times M\) 的矩形，左上角固定为 \((1,1)\)，计算的次数为 \(S(N,M)=\sum_{x=1}^N\sum_{y=1}^Mxy=\sum_{x=1}^Nx\sum_{y=1}^My=\frac {N(N+1)} 2\times \frac {M(M+1)} 2\) 。
因此，枚举左上角，在 \(O(1)\) 的时间统计左上角固定的矩阵需要计算的次数，最后的答案 \(ans=\sum_{i=1}^n\sum_{j=1}^mS(n-i+1,m-i+1)\) 。
时间复杂度为 \(O(n^2)\)。
\(80\) 分：
\(ans=\sum_{i=1}^n\sum_{j=1}^mS(n-i+1,m-i+1)=\sum_{i=1}^n\sum_{j=1}^mS(i,j)\)
展开后有 \(ans=\sum_{i=1}^n\sum_{j=1}^m \frac 1 4i(i+1)\times j(j+1)=\frac 1 4 \sum_{i=1}^ni(i+1) \sum_{j=1}^m j(j+1)\)
设 \(f(i)=\sum_{i=1}^ni(i+1)\) ，最后的答案 \(ans=\frac 1 4f(n)f(m)\) 。时间复杂度为 \(o(n)\) 。
\(100\) 分：
\(f(i)=\sum_{i=1}^ni(i+1)=\sum_{i=1}^ni^2 \sum_{i=1}^n(i+1)\)
\(\sum_{i=1}^ni^2=\frac 1 6n(n+1)(2n+1)\) (可用数学归纳法证明)
\(\sum_{i=1}^n(i+1)=\frac 1 2 n(n+1)\) 。
可以在 \(O(1)\) 的时间求解出答案。
时间限制：\(1s\)
空间限制：\(256MB\)
【题目描述】
\(AK\) 完了的小强又闲得无聊，于是开始随手在纸上用大写字母 \(A-Z\) 写下了一个字符串，然后他突然想到了一个问题，在这个字符串中，有多少个非空连续子串，其中 \(A\) 字符的数量， \(B\) 字符的数量和 \(C\) 字符的数量三个量相等。
【输入格式】
输入文件共一行，包含一个由大写字母 \(A-Z\) 构成的字符串 。
【输出格式】
输出文件共一行一个数字，代表有多少个符合条件的非空连续子串。
【样例输入】
ABACABA
【样例输出】
2
【样例解释】
\(S[2 ? 4]，S[4 ? 6]\) 。
【数据范围】
\(30\%\) 的数据 $|S| ≤ 100 $ 。
\(70\%\) 的数据 $|S| ≤ 1000 $ 。
\(100\%\) 的数据 \(|S| ≤ 10^6\)。
【算法分析】
\(30\) 分：
枚举非空连续子串两个端点，统计三种字符的个数。时间复杂度 \(O(N^3)\) 。
\(70\) 分：
使用前缀和 \(suma[i],sumb[i],sumc[i]\)，分别表示前 \(i\) 个字符，字符 \(A,B,C\) 的数量。可以在 \(O(1)\) 的时间统计两个端点之间三种字符的个数。时间复杂度为 \(O(N^2)\) 。
\(100\) 分：
设符合条件的非空连续子串区间为 \([l,r]\) 。则满足 suma[r]-suma[l-1]=sumb[r]-sumb[l-1]， sumb[r]-sumb[l-1]=sumc[r]-sumc[l-1]。
移项有 suma[r]-sumb[r]=suma[l-1]-sumb[l-1]， sumb[r]-sumc[r]=sumb[l-1]-sumc[l-1] 。
将 \(\{suma[i]-sumb[i],sumb[i]-sumc[i]\}\) 看作一个二元组，如果能找到一个相同的二元组\(\{suma[j]-sumb[j],sumb[j]-sumc[j]\}\) ，那么符号条件的非空连续子串的区间就是 \([i+1,j]（i<j）\) 。
从左到有遍历一遍，求出所有的二元组。再对二元组进行排序，二元组相同的排在相邻的位置，统计符合条件的个数。也可以一遍遍历一遍使用 \(map\) 存储。时间复杂度为 \(O(n\log n)\) 。
【题目描述】
\(2s,512MB\)
给定一个 \(n\times n\) 的矩形方格（横纵坐标都是 \(0\sim (n-1)\)）。一开始方格中的数均为 \(0\) ，你需要支持以下两种操作：
- 将给定的一个矩形中所有数 \(+1\) 。
- 询问给定一个矩形内所有数之和对 \(p\) 取模。
要求强制在线。
【输入格式】
第一行三个正整数 \(n,q,p\) 。
接下来 \(q\) 行，每行包含 \(5\) 个整数 \(type,w,x,y,z(1\le type\le 2,0\le w,x,y,z<n)\) 。
设 \(r\) 为到现在为止所有询问的答案和（**每个答案都是对 \(p\) 取模过的，最终把这些答案都求和，最终的 \(r\) 不模 \(p\) **）。
然后可以得到：
a=(w+r)%n; b=(x+r)%n; c=(y+r)%n; d=(z+r)%n; if(b<a)swap(a,b); if(d<c)swap(c,d);最终操作和询问的矩形为 \(\{(x,y)(a\le x, \le b,c\le y \le d\}\) 。
【输出格式】
对于每一个询问输出答案。
【样例输入】
3 11 10 1 0 2 0 0 1 1 2 2 2 1 0 2 1 1 2 0 1 1 2 1 2 2 0 1 1 0 1 2 2 1 0 2 0 2 2 0 2 0 1 1 2 1 0 0 1 2 1 0 1 2 2 1 2 1
【样例输出】
3 4 0
【样例解释】
解密以后的输入为：
3 11 10 1 0 2 0 0 1 1 2 2 2 1 0 2 1 1 2 0 1 1 2 1 2 2 0 1 1 0 1 2 2 1 0 2 0 2 2 0 2 0 1 1 0 2 1 1 1 0 2 1 2 2 0 2 0 2
【数据范围】
任务一：\(20\) 分，满足 \(n\le 10\) 。
任务二：\(40\) 分，满足 \(n\le 1000\) 。
任务三：\(40\) 分，无特殊限制。
对于所有数据有：\(2\le n \le 8000,1\le q\le 100000,1\le p\le 256\) 。
【问题分析】
二维树状数组
设原矩阵为 \(a_{i,j}\) ，对于子矩阵修改，使用二维差分，\(b_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}\) 。对矩阵 \((i,j)-(k,l)\) 增加 \(x\) ，只需要对二维差分数组修改四个点：\(b_{i,j}+=x,b_{k+1,j}-=x,b_{i,l+1}-=x,b_{k+1,l+1}+=x\) 。
二维差分数组的二维前缀和就是修改后的矩阵 \(a_{i,j}\) ，\(a_{i,j}=\sum_{i=1}^n\sum_{j=1}^mb_{i,j}\) 。
设 \(s_{i,j}\) 为矩阵 \(a_i,j\) 的二维前缀和，则矩阵 \((i,j)-(k,l)\) 中所有数的和为 \(s_{k,l}-s_{k,j-1}-s_{i-1,l}+s_{i-1,j-1}\) ，\(s_{i,j}=\sum_{i=1}^n\sum_{j=1}^ma_{i,j}\) 。
\(s_{n,m}=\sum_{i=1}^n\sum_{j=1}^ma_{i,j}\)
\(=\sum_{i=1}^n\sum_{j=1}^m\sum_{k=1}^i\sum_{l=1}^jb_{k,l}\)
\(=\sum_{k=1}^n\sum_{l=1}^m\sum_{i=k}^n\sum_{j=l}^mb_{k,l}\)
\(=\sum_{k=1}^n\sum_{l=1}^mb_{k,l}\times (n-k+1)(m-l+1)\)
\(=\sum_{i=1}^n\sum_{j=1}^mb_{i,j}\times (n-i+1)(m-i+1)\)
\(=(\sum_{k=1}^n\sum_{l=1}^mb_{i,j})\times (n+1)(m+1)-(\sum_{k=1}^n\sum_{l=1}^mib_{i,j})\times (m+1)-(\sum_{k=1}^n\sum_{l=1}^mjb_{i,j})\times (n+1)+(\sum_{k=1}^n\sum_{l=1}^mijb_{i,j})\)
因此，使用四个二维树状数组维护二维前缀和 \(b_{i,j},ib_{i,j},jb_{i,j},ijb_{i,j}\) 。
时间复杂度为 \(O(q\log n)\) 。
原文：https://www.cnblogs.com/strve/p/13829540.html