不加记忆化好像还要快一些QAQ
有没有大佬帮帮，不知道该怎么优化了，悬赏一个关注
by _WHITE_NIGHT_ @ 2023-09-04 10:41:32
线段树估计比较困难，建议您用ST（
然后建议把同步关掉用 cin 和 cout，不然大量输出字符串也会 T。
by MrcFrst_LRY @ 2023-09-04 11:09:54
（同机房大佬，%%%
by MrcFrst_LRY @ 2023-09-04 11:10:27
upd：一波操作之后，还是T，其他测试点已经从您原先900+ms优化到300+ms了（
by MrcFrst_LRY @ 2023-09-04 11:27:21
就是你应该用 unordered_map 而非 map，否则会多一个 log（
by MrcFrst_LRY @ 2023-09-04 11:28:14
这是改之后的代码：
```cpp
#include<bits/stdc++.h>
#define il inline
#define re register
using namespace std;
const int N = 2e5 + 5;
int n,m;
string ipt[N];
unordered_map <string,string> mp;
il string max(string a,string b)
{
string as = mp[a],bs = mp[b];
return as > bs ? a : b;
}
string change(string str)
{
if(mp.find(str) != mp.end()) return mp[str];
string tmp = str;
for(re int i = 0;i < str.length();i++)
if(str[i] >= 'A' && str[i] <= 'Z') str[i] = (str[i] - 'A' + 'a');
return mp[tmp] = str;
}
struct SegmentTree
{
struct node
{
int l,r;
string val;
#define l(pos) tree[pos].l
#define r(pos) tree[pos].r
#define val(pos) tree[pos].val
}tree[N << 2];
#define mid(pos) (tree[pos].l + tree[pos].r >> 1)
#define midn (l + r >> 1)
il void build(int l,int r,int pos)
{
l(pos) = l,r(pos) = r;
if(l == r) {val(pos) = ipt[l];return;}
build(l,midn,pos<<1);
build(midn+1,r,pos<<1|1);
val(pos) = max(val(pos<<1),val(pos<<1|1));
}
il string query(int l,int r,int pos)
{
if(l(pos) >= l && r >= r(pos)) return val(pos);
string ans;
if(l <= mid(pos)) ans = max(ans,query(l,r,pos<<1));
if(r > mid(pos)) ans = max(ans,query(l,r,pos<<1|1));
return ans;
}
#undef l
#undef r
#undef tag
#undef val
#undef mid
#undef midn
};
SegmentTree ST;
int main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(re int i = 1;i <= n;i++){
cin>>ipt[i];
mp[ipt[i]]=change(ipt[i]);
}
ST.build(1,n,1);
for(re int i = 1;i <= m;i++)
{
int a ,b;
cin>>a>>b;
cout << ST.query(a,b,1) << endl;
}
}
```
by MrcFrst_LRY @ 2023-09-04 11:32:12
@[HHYTomorrow](/user/601236) 试一下用 char 数组 + scanf 和 printf？可能会快一些。再卡卡常试试。
by Creeper_l @ 2023-09-04 12:11:22
膜拜卷皇%%%
by Creeper_l @ 2023-09-04 12:12:04
OK 谢谢，已关注QAQ
by _WHITE_NIGHT_ @ 2023-09-04 18:50:21