F. Digital Patterns：
题目描述：
思路解析：
要求在一个方块中，任意相邻的方块中他的透明度系数不能相同，这样的方块称为趣味性方块，问这样的方块有多少种。
那么我们可以相当，假设 a1 == a2, 那么每一列的第一行元素都等于第二行元素。 假设b1==b2，那么每一行的第一列元素都等于第二列元素。那么可以想到 a1 != a2, a3!=a2, b1 != b2, b2 != b3，那么就可以组成3*3的趣味性方块，并且其中2*2和1*1方块皆为趣味性方块。那么通过上述分析知道，只有出现相邻元素时，他们便无法组成趣味性方块。那么我们就可以将整个a数组和b数组分为多个区间块。
那么可以发现最后可以利用八个树状数组来维护a b c d这四个数组信息。
代码实现：
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
int t = 1;
while (t > 0) {
solve();
t--;
}
w.flush();
w.close();
}
static TreeSet<Integer> set[] = new TreeSet[2];
static Fenwick[][] fen = new Fenwick[2][4];
static int N;
static long ans;
public static void solve() throws IOException{
int n = f.nextInt(); int m = f.nextInt();
int q = f.nextInt();
ans = 0;
for (int i = 0; i < Math.min(n, m); i++) {
ans += (long) (n - i) * (m - i);
}
long[] a = new long[n+1];
long[] b = new long[m+1];
N = Math.max(n, m);
for (int i = 0; i < n; i++) {
a[i] = f.nextInt();
}
for (int i = 0; i < m; i++) {
b[i] = f.nextInt();
}
for (int i = 0; i < 2; i++) {
set[i] = new TreeSet<>();
for (int j = 0; j < 4; j++) {
fen[i][j] = new Fenwick(N+1);
}
}
set[0].add(0); set[0].add(n); set[1].add(0); set[1].add(m);
fen[0][0].add(n, 1);
fen[0][1].add(n, n);
fen[0][2].add(n, S1(n));
fen[0][3].add(n, S2(n));
fen[1][0].add(m, 1);
fen[1][1].add(m, m);
fen[1][2].add(m, S1(m));
fen[1][3].add(m, S2(m)); // 初始化
for (int i = n-1; i > 0; i--) {
a[i] -= a[i-1];
if (a[i] == 0){
insert(0, i);
}
}
for (int i = m-1; i > 0; i--) {
b[i] -= b[i-1];
if (b[i] == 0){
insert(1, i);
}
}
w.println(ans);
for (int i = 0; i < q; i++) {
int t = f.nextInt(); int l = f.nextInt() - 1; int r = f.nextInt(); int x = f.nextInt();
if (x == 0) continue;
if (t == 1){
if (l > 0){
if (a[l] == 0){
earse(0, l);
}
a[l] += x;
if (a[l] == 0){
insert(0, l);
}
}
if (r < n){
if (a[r] == 0){
earse(0, r);
}
a[r] -= x;
if (a[r] == 0){
insert(0, r);
}
}
}else {
if (l > 0){
if (b[l] == 0){
earse(1, l);
}
b[l] += x;
if (b[l] == 0){
insert(1, l);
}
}
if (r < m){
if (b[r] == 0){
earse(1, r);
}
b[r] -= x;
if (b[r] == 0){
insert(1, r);
}
}
}
w.println(ans);
}
}
public static void add(int t, int x, int coef){
ans +=(long) coef * x * fen[t ^ 1][2].sum(x); // n <= m
ans += (long) coef * fen[t ^ 1][3].sum(x);
// n <= m
ans += (long) coef * S2(x) * fen[t ^ 1][0].rangesum(x, N+1); // n > m
ans +=(long) coef * S1(x) * fen[t ^ 1][1].rangesum(x, N+1);
fen[t][0].add(x, coef);
fen[t][1].add(x, (long) coef *x);
fen[t][2].add(x, coef * S1(x));
fen[t][3].add(x, coef * S2(x));
}
public static void insert(int t, int i){
int l = set[t].floor(i);
int r = set[t].ceiling(i);
set[t].add(i);
add(t, r - l, -1);
add(t, i - l, 1);
add(t, r - i, 1);
}
public static void earse(int t, int i){
set[t].remove(i);
int l = set[t].floor(i);
int r = set[t].ceiling(i);
add(t, r - l, 1);
add(t, i - l, -1);
add(t, r - i, -1);
}
public static class Fenwick{
int n;
long[] a;
public Fenwick(int n){
this.n = n;
a = new long[n];
}
public void add(int x, long val){
for(int i = x+1; i <= n; i += i & -i) a[i-1] += val;
}
public long sum(int x){
long res = 0;
for (int i = x; i >= 1; i-= i & -i) {
res += a[i-1];
}
return res;
}
public long rangesum(int l, int r){
return sum(r) - sum(l);
}
}
public static long S1(int x) {return (long) x * (x + 1) / 2;}
public static long S2(int x) {return (long) x * (x + 1) * (2L * x + 1) / 6 - (long) x * x * (x+1L) / 2;}
static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
static Input f = new Input(System.in);
static class Input {
public BufferedReader reader;
public StringTokenizer tokenizer;
public Input(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() throws IOException{
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public long nextLong() throws IOException {
return Long.parseLong(next());
}
public Double nextDouble() throws IOException {
return Double.parseDouble(next());
}
}
}