7月

背单词
(word.c/cpp/pas)
【题目描述】
fqk 退役后开始补习文化课啦， 于是他打开了英语必修一开始背单
词。 看着满篇的单词非常头疼， 而每次按照相同的顺序背效果并不好，
于是 fqk 想了一种背单词的好方法！他把单词抄写到一个 n 行 m 列的
表格里，然后每天背一行或者背一列。他的复习计划一共有 k 天，在
k 天后， fqk 想知道，这个表格中的每个单词，最后一次背是在哪一
天呢？
【输入格式】
第一行三个整数 k m n , , 。
接下来 k 行，每行的格式可能如下：
1. r ，表示当前天 fqk 背了第 r 行的单词。
. 2 c ，表示当前天 fqk 背了第 c 列的单词。
【输出格式】
输出包含 n 行， 每行 m 个整数， 表示每个格子中的单词最后一次背
是在哪天，如果这个单词没有背过，则输出 0 。
【输入样例】
3 3 3
1 2
2 3
1 3
【输出样例】
0 0 2
1 1 2
3 3 3
【数据范围】
对于 % 30 的数据， 1000 , ,  k m n 。
对于 % 100 的数据， 100000 , 100000 , 5000 ,     k m n m n 。
【时空限制】
对于每个测试点，时间限制为 s 1 ,空间限制为 MB 512 。


开两个数组对于每一个点，记录行和列，输出时取max输出
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>

using namespace std;
const int N=5010;

int n,m,k;

int hang[N];
int lie[N];

inline int read()
{
    int x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

/*
第一行三个整数  n,m,k;
接下来 k 行，每行的格式可能如下：
1 r ，表示当前天 fqk 背了第 r 行的单词。
2 c ，表示当前天 fqk 背了第 c 列的单词
*/

int main()
{
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    n=read();
    m=read();
    k=read();
    for(int i=1;i<=k;i++)
    {
        int how=read();
        int num=read();
        if(how==1)//hang
            hang[num]=i;
        else//lie
            lie[num]=i;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            printf("%d ",max(hang[i],lie[j]));
        printf("
");
    }    
    return 0;
} 
/*
3 3 3
1 2
2 3
1 3
*/
脱水缩合
(merge.c/cpp/pas)
【题目描述】
fqk 退役后开始补习文化课啦， 于是他打开了生物必修一开始复习
蛋白质，他回想起了氨基酸通过脱水缩合生成肽键，具体来说，一个
氨基和一个羧基会脱去一个水变成一个肽键。于是他脑洞大开，给你
出了这样一道题：
fqk 将给你 6 种氨基酸和 m 个脱水缩合的规则，氨基酸用
' ' , ' ' , ' ' , ' ' , ' ' , ' ' f e d c b a 表示，每个规则将给出两个字符串 t s, ，其中
1 | | , 2 | |   t s ，表示 s 代表的两个氨基酸可以通过脱水缩合变成 t 。然后
请你构建一个长度为 n ,且仅由 ' ' , ' ' , ' ' , ' ' , ' ' , ' ' f e d c b a 构成的氨基酸序列，
如果这个序列的前两个氨基酸可以进行任意一种脱水缩合， 那么就可
以脱水缩合，脱水缩合后序列的长度将 1  ，这样如果可以进行 1  n 次
脱水缩合，最终序列的长度将变为 1 ，我们可以认为这是一个蛋白质，
如果最后的蛋白质为 ' 'a ， 那么初始的序列就被称为一个好的氨基酸序
列。 fqk 想让你求出有多少好的氨基酸序列。
注：题目描述可能与生物学知识有部分偏差（即氨基酸进行脱水
缩合后应该是肽链而不是新的氨基酸），请以题目描述为准。
【输入格式】
第一行两个整数 q n, 。
接下来 q 行，每行两个字符串 t s, ，表示一个脱水缩合的规则。
【输出格式】
一行，一个整数表示有多少好的氨基酸序列。
【输入样例】
3 5
ab a
cc c
ca a
ee c
ff d
【输出样例】
4
【样例解释】
一共有四种好的氨基酸序列，其脱水缩合过程如下：
"abb" "ab" "a"
"cab" "ab" "a"
"cca" "ca" "a"
"eea" "ca" "a"
【数据范围】
对于 % 100 的数据， 36 , 6 2    q n 。数据存在梯度。
【时空限制】
对于每个测试点，时间限制为 s 2 ,空间限制为 MB 512 。

首先打了个350+行的表，骗过3点不粘代码了，反正没啥意义：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<map>

using namespace std;

int n,m;
string ac;

string s[]={"aaa","aab","aac","aad","aae","aaf","aba","abb","abc","abd","abe","abf","aca","acb","acc","acd","ace","acf","ada","adb","adc","add","ade","adf","aea","aeb","aec","aed","aee","aef","afa","afb","afc","afd","afe","aff",
"baa","bab","bac","bad","bae","baf","bba","bbb","bbc","bbd","bbe","bbf","bca","bcb","bcc","bcd","bce","bcf","bda","bdb","bdc","bdd","bde","bdf","bea","beb","bec","bed","bee","bef","bfa","bfb","bfc","bfd","bfe","bff",
"caa","cab","cac","cad","cae","caf","cba","cbb","cbc","cbd","cbe","cbf","cca","ccb","ccc","ccd","cce","ccf","cda","cdb","cdc","cdd","cde","cdf","cea","ceb","cec","ced","cee","cef","cfa","cfb","cfc","cfd","cfe","cff",
"daa","dab","dac","dad","dae","daf","dba","dbb","dbc","dbd","dbe","dbf","dca","dcb","dcc","dcd","dce","dcf","dda","ddb","ddc","ddd","dde","ddf","dea","deb","dec","ded","dee","def","dfa","dfb","dfc","dfd","dfe","dff",
"eaa","eab","eac","ead","eae","eaf","eba","ebb","ebc","ebd","ebe","ebf","eca","ecb","ecc","ecd","ece","ecf","eda","edb","edc","edd","ede","edf","eea","eeb","eec","eed","eee","eef","efa","efb","efc","efd","efe","eff",
"faa","fab","fac","fad","fae","faf","fba","fbb","fbc","fbd","fbe","fbf","fca","fcb","fcc","fcd","fce","fcf","fda","fdb","fdc","fdd","fde","fdf","fea","feb","fec","fed","fee","fef","ffa","ffb","ffc","ffd","ffe","fff",
" ",
" "};

string _s[]={"aaaa","aaab","aaac","aaad","aaae","aaaf",
"aaba","aabb","aabc","aabd","aabe","aabf",
"aaca","aacb","aacc","aacd","aace","aacf",
"aada","aadb","aadc","aadd","aade","aadf",
"aaea","aaeb","aaec","aaed","aaee","aaef",
"aafa","aafb","aafc","aafd","aafe","aaff",

"abaa","abab","abac","abad","abae","abaf",
"abba","abbb","abbc","abbd","abbe","abbf",
"abca","abcb","abcc","abcd","abce","abcf",
"abda","abdb","abdc","abdd","abde","abdf",
"abea","abeb","abec","abed","abee","abef",
"abfa","abfb","abfc","abfd","abfe","abff",

"acaa","acab","acac","acad","acae","acaf",
"acba","acbb","acbc","acbd","acbe","acbf",
"acca","accb","accc","accd","acce","accf",
"acda","acdb","acdc","acdd","acde","acdf",
"acea","aceb","acec","aced","acee","acef",
"acfa","acfb","acfc","acfd","acfe","acff",

"adaa","adab","adac","adad","adae","adaf",
"adba","adbb","adbc","adbd","adbe","adbf",
"adca","adcb","adcc","adcd","adce","adcf",
"adda","addb","addc","addd","adde","addf",
"adea","adeb","adec","aded","adee","adef",
"adfa","adfb","adfc","adfd","adfe","adff",

"aeaa","aeab","aeac","aead","aeae","aeaf",
"aeba","aebb","aebc","aebd","aebe","aebf",
"aeca","aecb","aecc","aecd","aece","aecf",
"aeda","aedb","aedc","aedd","aede","aedf",
"aeea","aeeb","aeec","aeed","aeee","aeef",
"aefa","aefb","aefc","aefd","aefe","aeff",

"afaa","afab","afac","afad","afae","afaf",
"afba","afbb","afbc","afbd","afbe","afbf",
"afca","afcb","afcc","afcd","afce","afcf",
"afda","afdb","afdc","afdd","afde","afdf",
"afea","afeb","afec","afed","afee","afef",
"affa","affb","affc","affd","affe","afff",

"baaa","baab","baac","baad","baae","baaf",
"baba","babb","babc","babd","babe","babf",
"baca","bacb","bacc","bacd","bace","bacf",
"bada","badb","badc","badd","bade","badf",
"baea","baeb","baec","baed","baee","baef",
"bafa","bafb","bafc","bafd","bafe","baff",

"bbaa","bbab","bbac","bbad","bbae","bbaf",
"bbba","bbbb","bbbc","bbbd","bbbe","bbbf",
"bbca","bbcb","bbcc","bbcd","bbce","bbcf",
"bbda","bbdb","bbdc","bbdd","bbde","bbdf",
"bbea","bbeb","bbec","bbed","bbee","bbef",
"bbfa","bbfb","bbfc","bbfd","bbfe","bbff",

"bcaa","bcab","bcac","bcad","bcae","bcaf",
"bcba","bcbb","bcbc","bcbd","bcbe","bcbf",
"bcca","bccb","bccc","bccd","bcce","bccf",
"bcda","bcdb","bcdc","bcdd","bcde","bcdf",
"bcea","bceb","bcec","bced","bcee","bcef",
"bcfa","bcfb","bcfc","bcfd","bcfe","bcff",

"bdaa","bdab","bdac","bdad","bdae","bdaf",
"bdba","bdbb","bdbc","bdbd","bdbe","bdbf",
"bdca","bdcb","bdcc","bdcd","bdce","bdcf",
"bdda","bddb","bddc","bddd","bdde","bddf",
"bdea","bdeb","bdec","bded","bdee","bdef",
"bdfa","bdfb","bdfc","bdfd","bdfe","bdff",

"beaa","beab","beac","bead","beae","beaf",
"beba","bebb","bebc","bebd","bebe","bebf",
"beca","becb","becc","becd","bece","becf",
"beda","bedb","bedc","bedd","bede","bedf",
"beea","beeb","beec","beed","beee","beef",
"befa","befb","befc","befd","befe","beff",

"bfaa","bfab","bfac","bfad","bfae","bfaf",
"bfba","bfbb","bfbc","bfbd","bfbe","bfbf",
"bfca","bfcb","bfcc","bfcd","bfce","bfcf",
"bfda","bfdb","bfdc","bfdd","bfde","bfdf",
"bfea","bfeb","bfec","bfed","bfee","bfef",
"bffa","bffb","bffc","bffd","bffe","bfff",

"caaa","caab","caac","caad","caae","caaf",
"caba","cabb","cabc","cabd","cabe","cabf",
"caca","cacb","cacc","cacd","cace","cacf",
"cada","cadb","cadc","cadd","cade","cadf",
"caea","caeb","caec","caed","caee","caef",
"cafa","cafb","cafc","cafd","cafe","caff",

"cbaa","cbab","cbac","cbad","cbae","cbaf",
"cbba","cbbb","cbbc","cbbd","cbbe","cbbf",
"cbca","cbcb","cbcc","cbcd","cbce","cbcf",
"cbda","cbdb","cbdc","cbdd","cbde","cbdf",
"cbea","cbeb","cbec","cbed","cbee","cbef",
"cbfa","cbfb","cbfc","cbfd","cbfe","cbff",

"ccaa","ccab","ccac","ccad","ccae","ccaf",
"ccba","ccbb","ccbc","ccbd","ccbe","ccbf",
"ccca","cccb","cccc","cccd","ccce","cccf",
"ccda","ccdb","ccdc","ccdd","ccde","ccdf",
"ccea","cceb","ccec","cced","ccee","ccef",
"ccfa","ccfb","ccfc","ccfd","ccfe","ccff",

"cdaa","cdab","cdac","cdad","cdae","cdaf",
"cdba","cdbb","cdbc","cdbd","cdbe","cdbf",
"cdca","cdcb","cdcc","cdcd","cdce","cdcf",
"cdda","cddb","cddc","cddd","cdde","cddf",
"cdea","cdeb","cdec","cded","cdee","cdef",
"cdfa","cdfb","cdfc","cdfd","cdfe","cdff",

"ceaa","ceab","ceac","cead","ceae","ceaf",
"ceba","cebb","cebc","cebd","cebe","cebf",
"ceca","cecb","cecc","cecd","cece","cecf",
"ceda","cedb","cedc","cedd","cede","cedf",
"ceea","ceeb","ceec","ceed","ceee","ceef",
"cefa","cefb","cefc","cefd","cefe","ceff",

"cfaa","cfab","cfac","cfad","cfae","cfaf",
"cfba","cfbb","cfbc","cfbd","cfbe","cfbf",
"cfca","cfcb","cfcc","cfcd","cfce","cfcf",
"cfda","cfdb","cfdc","cfdd","cfde","cfdf",
"cfea","cfeb","cfec","cfed","cfee","cfef",
"cffa","cffb","cffc","cffd","cffe","cfff",

"daaa","daab","daac","daad","daae","daaf",
"daba","dabb","dabc","dabd","dabe","dabf",
"daca","dacb","dacc","dacd","dace","dacf",
"dada","dadb","dadc","dadd","dade","dadf",
"daea","daeb","daec","daed","daee","daef",
"dafa","dafb","dafc","dafd","dafe","daff",

"dbaa","dbab","dbac","dbad","dbae","dbaf",
"dbba","dbbb","dbbc","dbbd","dbbe","dbbf",
"dbca","dbcb","dbcc","dbcd","dbce","dbcf",
"dbda","dbdb","dbdc","dbdd","dbde","dbdf",
"dbea","dbeb","dbec","dbed","dbee","dbef",
"dbfa","dbfb","dbfc","dbfd","dbfe","dbff",

"dcaa","dcab","dcac","dcad","dcae","dcaf",
"dcba","dcbb","dcbc","dcbd","dcbe","dcbf",
"dcca","dccb","dccc","dccd","dcce","dccf",
"dcda","dcdb","dcdc","dcdd","dcde","dcdf",
"dcea","dceb","dcec","dced","dcee","dcef",
"dcfa","dcfb","dcfc","dcfd","dcfe","dcff",

"ddaa","ddab","ddac","ddad","ddae","ddaf",
"ddba","ddbb","ddbc","ddbd","ddbe","ddbf",
"ddca","ddcb","ddcc","ddcd","ddce","ddcf",
"ddda","dddb","dddc","dddd","ddde","dddf",
"ddea","ddeb","ddec","dded","ddee","ddef",
"ddfa","ddfb","ddfc","ddfd","ddfe","ddff",

"deaa","deab","deac","dead","deae","deaf",
"deba","debb","debc","debd","debe","debf",
"deca","decb","decc","decd","dece","decf",
"deda","dedb","dedc","dedd","dede","dedf",
"deea","deeb","deec","deed","deee","deef",
"defa","defb","defc","defd","defe","deff",

"dfaa","dfab","dfac","dfad","dfae","dfaf",
"dfba","dfbb","dfbc","dfbd","dfbe","dfbf",
"dfca","dfcb","dfcc","dfcd","dfce","dfcf",
"dfda","dfdb","dfdc","dfdd","dfde","dfdf",
"dfea","dfeb","dfec","dfed","dfee","dfef",
"dffa","dffb","dffc","dffd","dffe","dfff",

"eaaa","eaab","eaac","eaad","eaae","eaaf",
"eaba","eabb","eabc","eabd","eabe","eabf",
"eaca","eacb","eacc","eacd","eace","eacf",
"eada","eadb","eadc","eadd","eade","eadf",
"eaea","eaeb","eaec","eaed","eaee","eaef",
"eafa","eafb","eafc","eafd","eafe","eaff",

"ebaa","ebab","ebac","ebad","ebae","ebaf",
"ebba","ebbb","ebbc","ebbd","ebbe","ebbf",
"ebca","ebcb","ebcc","ebcd","ebce","ebcf",
"ebda","ebdb","ebdc","ebdd","ebde","ebdf",
"ebea","ebeb","ebec","ebed","ebee","ebef",
"ebfa","ebfb","ebfc","ebfd","ebfe","ebff",

"ecaa","ecab","ecac","ecad","ecae","ecaf",
"ecba","ecbb","ecbc","ecbd","ecbe","ecbf",
"ecca","eccb","eccc","eccd","ecce","eccf",
"ecda","ecdb","ecdc","ecdd","ecde","ecdf",
"ecea","eceb","ecec","eced","ecee","ecef",
"ecfa","ecfb","ecfc","ecfd","ecfe","ecff",

"edaa","edab","edac","edad","edae","edaf",
"edba","edbb","edbc","edbd","edbe","edbf",
"edca","edcb","edcc","edcd","edce","edcf",
"edda","eddb","eddc","eddd","edde","eddf",
"edea","edeb","edec","eded","edee","edef",
"edfa","edfb","edfc","edfd","edfe","edff",

"eeaa","eeab","eeac","eead","eeae","eeaf",
"eeba","eebb","eebc","eebd","eebe","eebf",
"eeca","eecb","eecc","eecd","eece","eecf",
"eeda","eedb","eedc","eedd","eede","eedf",
"eeea","eeeb","eeec","eeed","eeee","eeef",
"eefa","eefb","eefc","eefd","eefe","eeff",

"efaa","efab","efac","efad","efae","efaf",
"efba","efbb","efbc","efbd","efbe","efbf",
"efca","efcb","efcc","efcd","efce","efcf",
"efda","efdb","efdc","efdd","efde","efdf",
"efea","efeb","efec","efed","efee","efef",
"effa","effb","effc","effd","effe","efff",

"faaa","faab","faac","faad","faae","faaf",
"faba","fabb","fabc","fabd","fabe","fabf",
"faca","facb","facc","facd","face","facf",
"fada","fadb","fadc","fadd","fade","fadf",
"faea","faeb","faec","faed","faee","faef",
"fafa","fafb","fafc","fafd","fafe","faff",

"fbaa","fbab","fbac","fbad","fbae","fbaf",
"fbba","fbbb","fbbc","fbbd","fbbe","fbbf",
"fbca","fbcb","fbcc","fbcd","fbce","fbcf",
"fbda","fbdb","fbdc","fbdd","fbde","fbdf",
"fbea","fbeb","fbec","fbed","fbee","fbef",
"fbfa","fbfb","fbfc","fbfd","fbfe","fbff",

"fcaa","fcab","fcac","fcad","fcae","fcaf",
"fcba","fcbb","fcbc","fcbd","fcbe","fcbf",
"fcca","fccb","fccc","fccd","fcce","fccf",
"fcda","fcdb","fcdc","fcdd","fcde","fcdf",
"fcea","fceb","fcec","fced","fcee","fcef",
"fcfa","fcfb","fcfc","fcfd","fcfe","fcff",

"fdaa","fdab","fdac","fdad","fdae","fdaf",
"fdba","fdbb","fdbc","fdbd","fdbe","fdbf",
"fdca","fdcb","fdcc","fdcd","fdce","fdcf",
"fdda","fddb","fddc","fddd","fdde","fddf",
"fdea","fdeb","fdec","fded","fdee","fdef",
"fdfa","fdfb","fdfc","fdfd","fdfe","fdff",

"feaa","feab","feac","fead","feae","feaf",
"feba","febb","febc","febd","febe","febf",
"feca","fecb","fecc","fecd","fece","fecf",
"feda","fedb","fedc","fedd","fede","fedf",
"feea","feeb","feec","feed","feee","feef",
"fefa","fefb","fefc","fefd","fefe","feff",

"ffaa","ffab","ffac","ffad","ffae","ffaf",
"ffba","ffbb","ffbc","ffbd","ffbe","ffbf",
"ffca","ffcb","ffcc","ffcd","ffce","ffcf",
"ffda","ffdb","ffdc","ffdd","ffde","ffdf",
"ffea","ffeb","ffec","ffed","ffee","ffef",
"fffa","fffb","fffc","fffd","fffe","ffff",

" "," "
};

inline int read()
{
int x=0;int f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x*f;
}

int main()
{
freopen("merge.in","r",stdin);
freopen("merge.out","w",stdout);
n=read();
m=read();
if(n==2)
{
int answer(0);
string sss,ss;
for(int i=1;i<=m;i++)
{
cin>>sss>>ss;//不读空格，不读回车
if(ss=="a")
answer++;
}
printf("%d",answer);
return 0;
}
if(n==3)
{
int answer=0;
string s1,s2;
map<string,string>mp;
for(int i=1;i<=m;i++)
{
cin>>s1>>s2;
mp[s1]=s2;
}
for(int i=0;i<216;i++)
{
ac.clear();
ac+=s[i][0];
ac+=s[i][1];
ac=mp[ac];
ac+=s[i][2];
if(mp[ac]=="a")
answer++;
}
printf("%d",answer);
return 0;
}
if(n==4)
{
int answer=0;
string s1,s2;
map<string,string>mp;
for(int i=1;i<=m;i++)
{
cin>>s1>>s2;
mp[s1]=s2;
}
for(int i=0;i<1296;i++)
{
ac.clear();
ac+=_s[i][0];
ac+=_s[i][1];
ac=mp[ac];
ac+=_s[i][2];
ac=mp[ac];
ac+=_s[i][3];
ac=mp[ac];
if(ac=="a")
answer++;
}
printf("%d",answer);
return 0;
}
else
{
printf("78");
}
return 0;

}

正解：dfs，深搜出每一种情况，对于每一种情况进行判断，记录答案：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define N 40
using namespace std;

int n,q,ans(0);
char s[N][3],t[N][2],a[N];

bool pd(int k) 
{ //判断根据规则能否构成现在的组合方式
    if (k==n&&a[k]=='a') return 1;
    for (int i=1; i<=q; i++)
        if (s[i][1]==a[k]&&s[i][2]==a[k+1]) 
        {
            int ki=a[k+1];
            a[k+1]=t[i][1];
            bool ff=pd(k+1);
            a[k+1]=ki;
            if (ff) return 1;
        }
    return 0;
}

void dfs(int k) 
{  //枚举每一种组合方式
    if (k==n+1) 
    {
        if (pd(1)) ans++;
        return ;
    }
    for (int i=0; i<=6; i++) 
    {
        a[k]=i+'a';
        dfs(k+1);
    }
}

int main() 
{
    freopen("merge.in","r",stdin);
    freopen("merge.out","w",stdout);
    scanf("%d%d",&n,&q);
    for (int i=1; i<=q; i++) 
    {
        scanf("%s",s[i]+1);
        scanf("%s",t[i]+1);
    }
    dfs(1);
    cout<<ans<<endl;
    return 0;
}



一次函数
（fx.c/cpp/pas)
【题目描述】
fqk 退役后开始补习文化课啦， 于是他打开了数学必修一开始复习
函数， 他回想起了一次函数都是 b kx x f   ) ( 的形式， 现在他给了你 n 个
一次函数
i i i
b x k x f   ) ( ， 然后将给你 m 个操作， 操作将以如下格式给出：
M . 1 i k b ，把第 i 个函数改为 b kx x f i   ) ( 。
Q . 2 l r x ，询问 ))) ( (... (
1
x f f f
l r r 
mod 1000000007 的值。
【输入格式】
第一行两个整数 n ， m ，代表一次函数的数量和操作的数量。
接下来 n 行，每行两个整数，表示
i
k ，
i
b 。
接下来 m 行，每行的格式为 M i k b 或 Q l r x 。
【输出格式】
对于每个操作 Q ，输出一行表示答案。
【输入样例】
5 5
4 2
3 6
5 7
2 6
7 5
Q 1 5 1
Q 3 3 2
M 3 10 6
Q 1 4 3
Q 3 4 4
【输出样例】
1825
17
978
98
【数据范围】
对于 % 30 的数据， 1000 ,  m n 。
对于 % 100 的数据， 1000000007 , , , 200000 ,   x b k m n 。
【时空限制】
对于每个测试点，时间限制为 s 2 ,空间限制为 MB 512 。

一开始我推了个公式，然而花了1h未能实现，放弃，暴力20；
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long

using namespace std;
const int N=200010;
const int mod=1000000007;

LL k[N],b[N];
LL n,m;
char how;

inline LL read()
{
    LL x=0;LL f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

LL calc(LL l,LL r,LL x)
{
    LL answer=0;
    answer=(k[l]*x%mod+b[l]%mod)%mod;
    for(int i=l+1;i<=r;i++)
        answer=(k[i]*answer%mod+b[i]%mod)%mod;
    return answer;
}

int main()
{
    freopen("fx.in","r",stdin);
    freopen("fx.out","w",stdout);
    n=read();
    m=read();
    for(int i=1;i<=n;i++)
    {
        k[i]=read();
        b[i]=read();
    }
    for(int i=1;i<=m;i++)
    {
        cin>>how;
        if(how=='M')
        {
            int ii=read(),kk=read(),bb=read();
            k[ii]=kk;
            b[ii]=bb;
        }
        else
        {
            LL l=read(),r=read(),x=read();
            printf("%lld
",calc(l,r,x));
        }
    }
    return 0;
}
/*
5 5
4 2
3 6
5 7
2 6
7 5
Q 1 5 1
Q 3 3 2
M 3 10 6
Q 1 4 3
Q 3 4 4
*/













正解是线段树，然而我还真没想到是线段树
参考代码：
//维护 k,b 合并时手推一下
//简单的数学知识
#include<cstdio>
#include<iostream>
#define mod 1000000007
#define ll long long
#define lc now*2
#define rc now*2+1
#define mid (l+r)/2
#define maxn 200010
using namespace std;
int n,m;
ll K[maxn*4],B[maxn*4];
char s[5];
inline int read(){
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
inline void build(int now,int l,int r,int x,int a,int b){
    if(l==r){
        K[now]=a;B[now]=b;return;
    }
    if(x<=mid)build(lc,l,mid,x,a,b);
    else build(rc,mid+1,r,x,a,b);
    K[now]=K[lc]*K[rc]%mod;B[now]=(K[rc]*B[lc]%mod+B[rc])%mod;
}
inline ll query1(int now,int l,int r,int x,int y){
    if(x<=l&&y>=r)return K[now];
    if(y<=mid)return query1(lc,l,mid,x,y);
    else if(x>mid)return query1(rc,mid+1,r,x,y);
    else{
        ll kl=query1(lc,l,mid,x,y);
        ll kr=query1(rc,mid+1,r,x,y);
        return kl*kr%mod;
    }
}
inline ll query2(int now,int l,int r,int x,int y){
    if(x<=l&&y>=r)return B[now];
    if(y<=mid)return query2(lc,l,mid,x,y);
    else if(x>mid)return query2(rc,mid+1,r,x,y);
    else{
        ll bl=query2(lc,l,mid,x,y);
        ll br=query2(rc,mid+1,r,x,y);
        ll kr=query1(rc,mid+1,r,x,y);
        return (kr*bl%mod+br)%mod;
    }
}
int main() {
    freopen("fx.in","r",stdin);
    freopen("fx.out","w",stdout);
    n=read();m=read();ll x,y,z;
    for(int i=1;i<=n;i++){
        x=read();y=read();
        build(1,1,n,i,x,y);
    }
    for(int i=1;i<=m;i++){
        scanf("%s",s);x=read();y=read();z=read();
        if(s[0]=='M')build(1,1,n,x,y,z);
        else if(s[0]=='Q'){
            ll kk=query1(1,1,n,x,y);
            ll bb=query2(1,1,n,x,y);
            cout<<(kk*z%mod+bb)%mod<<endl;
        }
    }
    return 0;
}