5392: Interval Queries
内存限制：128 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
Given a sequence A of length n and q quries. For each query, three integers l,r,k are given and you should calculate:
∑f({Al−i,...,Al,Al+1,...,Ar,...,Ar+i})×(n+1)^i(mod998244353)(i from 0 to k-1),wherf(S)=max{len∣∃x,∀u∈{x,x+1,⋯,x+len−1},u∈S}
∑f({Al−i,...,Al,Al+1,...,Ar,...,Ar+i})×(n+1)^i(mod998244353)(i from 0 to k-1),wherf(S)=max{len∣∃x,∀u∈{x,x+1,⋯,x+len−1},u∈S}
输入
The first line contains two integers n,q (1≤n,q≤105), denoting the length of given sequence and the number of quries respectively.
The second line contains n integers A1,A2,⋯,An (1≤Ai≤n) denoting the given sequence.Following q lines each contains three integers l,r,k (1≤l−k+1≤l≤r≤r+k−1≤n) denoting each query.
It's guaranteed that ∑k≤107.
输出
Output q lines each containing one integer, denoting the answers to the queries.
样例输入 复制
5 2
2 4 1 5 3
3 4 2
3 3 3样例输出 复制
19
193提示
For the first query, f({A3,A4})=f({1,5})=1,f({A2,A3,A4,A5})=f({4,1,5,3})=3, so the answer is 1×6^0+3×6^1=1+18=19.For the second query, f({A3})=f({1})=1,f({A2,A3,A4})=f({4,1,5})=2,f({A1,A2,A3,A4,A5})=f({2,4,1,5,3})=5f({A3})=f({1})=1. so the answer is 1×6^0+2×6^1+5×6^2=1+12+180=193.