QAQ & 君臨天下 || 天行九歌

Description

QAQ~生活之余喜歡看一些動(dòng)漫，說(shuō)到國(guó)產(chǎn)動(dòng)漫，QAQ 最喜歡的就屬玄機(jī)了，玄機(jī)出品的動(dòng)漫都很贊的說(shuō)，君臨天下 和 天行九歌是 QAQ 最喜歡的兩部動(dòng)漫了，每次看完 QAQ 對(duì)玄機(jī)的敬佩值都會(huì)分別增加 2 與 1，QAQ 記錄了自己每天看的動(dòng)漫名稱 由 A ~ Z 26個(gè)字母代替，J ：代表 君臨天下，T 代表 ： 天行九歌。
有一天，ORZ 突發(fā)奇想想幫 QAQ 測(cè)試一下 L ~ R 天里 QAQ 對(duì)玄機(jī)的敬佩值增加了多少，看 QAQ 能否清楚記得？

問(wèn)題來(lái)了 ORZ 怎么知道 QAQ 回答的對(duì)錯(cuò)呢 ？所以 ORZ 想請(qǐng)你幫忙算出 L ~ R 天里 QAQ 對(duì)玄機(jī)的敬佩值增加的正確答案。

Input

第一行一個(gè) T （ 1≤T≤101≤T≤10）代表有 T 組測(cè)試數(shù)據(jù)

第二行兩個(gè)數(shù) n ,m (1≤n,m≤1051≤n,m≤105),分別代表看了 n 天動(dòng)漫，和 m 次查詢

接下來(lái) n 行一個(gè) A ~ Z 的字母，表示第 i 天看的動(dòng)漫名稱

接下來(lái) m 行，每行兩個(gè)數(shù) L,R (1≤L≤R≤n1≤L≤R≤n)

Output

對(duì)于每次查詢，輸出 L~R 天里，QAQ對(duì)玄機(jī)的敬佩值增加了多少

樣例輸入

Sample Input

1 3 3 J A T 1 1 1 2 2 3

Sample Output

2 2 1

題解：

這個(gè)大水題放上來(lái)的唯一原因是因?yàn)楸┝δ芷H過(guò)去的讓蒟蒻寫成樹狀數(shù)組模板TAT

AC代碼

#include <bits/stdc++.h> using namespace std; #define N 500500 int a[N], c[N]; int n, m; int lowbit(int x) {return x&(-x); } void update(int p, int x) {while(p <= n) {c[p] += x;p += lowbit(p);} } int sum(int p) {int sum = 0;while(p > 0) {sum += c[p];p -= lowbit(p);} return sum; } int main() {int T;char str[10];int u, v;int k = 0;scanf("%d",&T);while(T--) {int x;memset(a,0,sizeof(a));memset(c,0,sizeof(c));scanf("%d%d",&n,&m);for(int i = 1;i <= n; i++) {scanf("%d",&x);scanf("%s",str);if(str[0] == 'J') x = 2;else if(str[0] == 'T') x = 1;else x = 0;a[i] += x;update(i,x);}while(m--) {scanf("%d%d",&u,&v);printf("%d\n",sum(v)-sum(u-1));}} return 0; }

總結(jié)

以上是生活随笔為你收集整理的1412: QAQ 君临天下 || 天行九歌 [区间]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。