题目
点这里看题目。
分析
考虑将所有子序列画成(n imes n)的表的形式，表中的元素((x,y))就表示子序列(a[x:y])的最小值。（(x>y)则((x,y)=0)）
那么，对于一个元素(a_i)，记它左边第一个小于它的位置为(lef(i))，右边第一个小于等于它的位置为(rig(i))。那么，在表格中，从((lef(i)+1,i))到((i,rig(i)-1))的这些序列的最小值，都会是(a_i)。因此，一个元素就相当于在这个表格上面进行了一次矩形覆盖。
再考虑查询，对于查询((l,r))，它查询的实际就是表格上((l,l))到((r,r))的元素和。考虑到(forall 1le i< l, lle jle r, (j,i)=0)，因此，询问实际上等价于((l,1))到((r,r))的元素和。
接下来就是一个离线的扫描线问题了。将矩形覆盖分为两类，一类是已经被扫描线扫过了，一类是正在被扫描。对于第一类，我们可以用一个线段树(T_1)维护它的贡献（因为扫过了之后它的贡献就不会改变了）；对于第二类，我们做一个差分，将它已经固定了的贡献((lef-1)*a)加入到(T_1)中，再用另一个线段树(T_2)维护当前扫描线上的情况。查询的时候，我们就可以将(T_2)的贡献乘上扫描线的位置，再与(T_1)的贡献相加，这样第二类矩形的贡献就可以算出来了。
时间是(O(nlog_2n))。
代码
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5;
template<typename _T>
void read( _T &x )
{
x = 0;char s = getchar();int f = 1;
while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
x *= f;
}
template<typename _T>
void write( _T x )
{
if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
if( 9 < x ){ write( x / 10 ); }
putchar( x % 10 + '0' );
}
struct SegmentTree
{
LL s[MAXN << 2], tag[MAXN << 2];
SegmentTree() { memset( s, 0, sizeof s ), memset( tag, 0, sizeof tag ); }
void upt( const int x ) { s[x] = s[x << 1] + s[x << 1 | 1]; }
void add( const int x, const LL v, const int l, const int r ) { s[x] += ( r - l + 1 ) * v, tag[x] += v; }
void normalize( const int x, const int l, const int r )
{
if( ! tag[x] ) return ;
int mid = l + r >> 1;
add( x << 1, tag[x], l, mid ), add( x << 1 | 1, tag[x], mid + 1, r );
tag[x] = 0;
}
void update( const int u, const int l, const int r, const int segL, const int segR, const LL val )
{
if( segL <= l && r <= segR ) { add( u, val, l, r ); return ; }
int mid = l + r >> 1; normalize( u, l, r );
if( segL <= mid ) update( u << 1, l, mid, segL, segR, val );
if( segR > mid ) update( u << 1 | 1, mid + 1, r, segL, segR, val );
upt( u );
}
LL query( const int u, const int l, const int r, const int segL, const int segR )
{
if( segL <= l && r <= segR ) return s[u];
LL ret = 0; int mid = l + r >> 1; normalize( u, l, r );
if( segL <= mid ) ret += query( u << 1, l, mid, segL, segR );
if( mid < segR ) ret += query( u << 1 | 1, mid + 1, r, segL, segR );
return ret;
}
}T1, T2;
vector<int> add[MAXN], sub[MAXN], q[MAXN];
LL ans[MAXN], qL[MAXN], qR[MAXN];
int a[MAXN], lef[MAXN], rig[MAXN], stk[MAXN];
int N, Q, top;
signed main()
{
read( N ), read( Q );
for( int i = 1 ; i <= N ; i ++ ) read( a[i] );
for( int i = 1 ; i <= N ; i ++ )
{
while( top && a[stk[top]] >= a[i] ) rig[stk[top --]] = i;
stk[++ top] = i;
}
while( top ) rig[stk[top --]] = N + 1;
for( int i = N ; i ; i -- )
{
while( top && a[stk[top]] > a[i] ) lef[stk[top --]] = i;
stk[++ top] = i;
}
while( top ) lef[stk[top --]] = 0;
for( int i = 1 ; i <= N ; i ++ ) add[i].push_back( i ), sub[rig[i]].push_back( i );
for( int i = 1 ; i <= Q ; i ++ )
{
read( qL[i] ), read( qR[i] );
q[qR[i]].push_back( i );
}
int id;
for( int i = 1 ; i <= N ; i ++ )
{
for( int j = 0 ; j < add[i].size() ; j ++ )
{
id = add[i][j];
T1.update( 1, 1, N, lef[id] + 1, id, 1ll * ( i - 1 ) * a[id] );
T2.update( 1, 1, N, lef[id] + 1, id, a[id] );
}
for( int j = 0 ; j < sub[i].size() ; j ++ )
{
id = sub[i][j];
T1.update( 1, 1, N, lef[id] + 1, id, -1ll * ( i - 1 ) * a[id] );
T2.update( 1, 1, N, lef[id] + 1, id, - a[id] );
}
for( int j = 0 ; j < q[i].size() ; j ++ )
{
id = q[i][j];
ans[id] = 1ll * i * T2.query( 1, 1, N, qL[id], qR[id] ) - T1.query( 1, 1, N, qL[id], qR[id] );
}
}
for( int i = 1 ; i <= Q ; i ++ ) write( ans[i] ), putchar( '
' );
return 0;
}