2463. 纸牌PK
1000ms
256MB
简单
前缀和与差分
题目描述
阿玛特拉斯和小鸟伏特加每次遇到谁优先的问题，都会采用抽一张纸牌比大小的方式决定，总采用这种方式，难免感到无趣。
今天阿玛特拉斯突发奇想，修改了抽纸牌的方式：两人轮流在 $n$ 张纸牌中抽取 $m$ 轮，每轮抽取连续一定范围的纸牌，计算 $m$ 轮抽取中所有牌面上的数字总和，最终谁的数字总和越大，谁获得优先权。
输入格式
- 第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 500,000, 1 \le m \le 100$)。
- 第二行包含 $n$ 个整数，依次表示 $n$ 张纸牌上的数字 ($1 \le \text{整数} \le 100$)。
- 接下来 $m$ 行，每行两个正整数 $L$ 和 $R$，表示**阿玛特拉斯**每轮抽牌的范围。
- 再接下来 $m$ 行，每行两个正整数 $L$ 和 $R$，表示**小鸟伏特加**每轮抽牌的范围 ($1 \le L \le R \le n$)。
输出格式
- 输出一个字符：
- 若阿玛特拉斯数字总和更大，输出 `T`；
- 若小鸟伏特加数字总和更大，输出 `C`；
- 若总和相等，输出 `D`。
样例 1
输入 (Input)
输出 (Output)
样例说明
输入样例中 $m=3$，表示两人各自抽 3 轮范围纸牌。
**阿玛特拉斯：**
- 第 1 轮：3~5，和为 $5+3+6=14$。
- 第 2 轮：6~7，和为 $4+9=13$。
- 第 3 轮：2~7，和为 $10+5+3+6+4+9=37$。
- 总和为 $14+13+37=64$。
**小鸟伏特加：**
- 第 1 轮：2~6，和为 $10+5+3+6+4=28$。
- 第 2 轮：1~2，和为 $2+10=12$。
- 第 3 轮：1~6，和为 $2+10+5+3+6+4=30$。
- 总和为 $28+12+30=70$。
最终小鸟伏特加总和大于阿玛特拉斯，输出字符 `C`。
- $n \le 500,000$，$m \le 100$。
- 纸牌数字 $\le 100$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功