题意

有一群从 至 编号的防御塔，每个防御塔会有一个护盾，防御力是 。每一次，敌人会从 到 的他进行 的打击。这时候会将 若 小于等于0，就是这次护盾破了，之后收到的伤害会加倍，在此之前，受到的伤害是一倍。

你需要支持单点查询这个点收到的伤害。并支持区间打击。

树状数组-离线

考虑对于打击差分，由编号求解，对于时间建立树状数组。将打击和询问对于编号排序，我们每次只要处理出来一个编号的点所有的答案即可。

就是说，每次的打击如果是 到 的 ，此时时刻是 ，那么，就在 的树状数组上记一下，在做到编号是 的时候加 ，在做到 的时候减 。

比如下边这个样例：

5 8
1 2 3 4 5
A 1 3 2
A 1 4 1
Q 2
A 1 4 1
Q 1
A 1 4 1
Q 2
Q 4

图片说明

正如上图所示，我们差分之后做一个前缀和，就可以得到每个时刻每个点的值。不难二分出来打破盾的位置，以计算答案。

这种做法的时间复杂度是 ，但是实际上跑不到，所以和后边的 速度相差不远。

示例代码

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::pair;
using std::make_pair;
#define For( i, j, k ) for( int i = j; i <= k; ++i )
#ifdef ONLINE_JUDGE
const int N = 210000, mod = 1e9 + 9;
#else
const int N = 100, mod = 1e9 + 9;
#endif
char ch; 
int n, q, a[ N ], tot, num;
pair < int, pair < int, int > > p[ N * 2 ];
pair < int, int > Q[ N ];
long long Sc[ N ], ans[ N ];
long long sum( int x )
{
 long long res = 0;
 while( x )
  res += Sc[ x ],
  x -= x & -x;
 return res;
}
void Add( int x, int d )
{
 while( x <= q )
 {
  Sc[ x ] += d;
  x += x & -x;
 }
 return;
}
void Solve( )
{
 int cur1 = 1, cur2 = 1;
 For( i, 1, n )
 {
  while( p[ cur1 ].first == i && cur1 <= tot )
   Add( p[ cur1 ].second.first, p[ cur1 ].second.second ), ++cur1;
  while( Q[ cur2 ].first == i && cur2 <= num )
  {
   int L = 1, R = Q[ cur2 ].second, IO = Q[ cur2 ].second;
   long long S;
   while( L <= R )
   {
    int mid = L + R >> 1;
    if( sum( mid ) >= a[ i ] )
     IO = mid, R = mid - 1;
    else
     L = mid + 1;
   }
   S = sum( IO );
   ans[ Q[ cur2 ].second ] = S + ( sum( Q[ cur2 ].second ) - sum( IO ) ) * 2;
   ++cur2;
  }
 }
 return;
}
int main( )
{
 std::ios::sync_with_stdio( false );
 cin.tie( 0 );
 cout.tie( 0 );
 cin >> n >> q;
 For( i, 1, n )
  cin >> a[ i ];
 int l, r, c;
 For( i, 1, q )
 {
  cin >> ch;
  if( ch == 'Q' )
   cin >> l,
   Q[ ++num ] = make_pair( l, i );
  else
   cin >> l >> r >> c,
   p[ ++tot ] = make_pair( l, make_pair( i, c ) ),
   p[ ++tot ] = make_pair( r + 1, make_pair( i, -c ) );
 }
 std::sort( p + 1, p + tot + 1 );
 std::sort( Q + 1, Q + num + 1 );
 memset( ans, -1, sizeof ans );
 Solve( );
 long long ANS = 0;
 For( i, 1, q ) if( ~ans[ i ] )
  ANS = ( ans[ i ] + ANS ) % mod;
 cout << ANS;
 return 0;
}

线段树-可在线

势能线段树 

#include <bits/stdc++.h>
#define For( i, j, k ) for( int i = j; i <= k; ++i )
#define Rep( i, j, k ) for( int i = j; i >= k; --i )
using std::cin;
using std::cout;
inline int ls( int k ) { return k << 1; }
inline int rs( int k ) { return k << 1 | 1; }
const int N = 1e5 + 1, MOD = 1e9 + 9;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int n, q, a[ N ];
long long ANS;
char ch;
struct Node
{
 int l, r;
 long long mn, tag;
}elvahs[ N * 4 ];
#define l( i ) elvahs[ i ].l
#define r( i ) elvahs[ i ].r
#define mn( i ) elvahs[ i ].mn
#define tag( i ) elvahs[ i ].tag
inline void Up( int k ) { mn( k ) = std::min( mn( ls( k ) ), mn( rs( k ) ) ); }
inline void PutTag( int k, long long x ) { mn( k ) -= x; tag( k ) += x; }
inline void Down( int k ) { if( tag( k ) ) PutTag( ls( k ), tag( k ) ), PutTag( rs( k ), tag( k ) ), tag( k ) = 0; }
void Build( int k, int l, int r )
{
 l( k ) = l, r( k ) = r;
 if( l == r )
 {
  mn( k ) = a[ l ];
  return;
 }
 int mid = l + r >> 1;
 return Build( ls( k ), l, mid ), Build( rs( k ), mid + 1, r ), Up( k );
}
void Modify( int k, int l, int r, int d )
{
 if( l <= l( k ) && r( k ) <= r && mn( k ) > d )
  return PutTag( k, d );
 if( l( k ) == r( k ) )
 {
  a[ l( k ) ] += d - mn( k );
  mn( k ) = INF;
  return;
 }
 Down( k );
 int mid = l( k ) + r( k ) >> 1;
 if( l <= mid )
  Modify( ls( k ), l, r, d );
 if( mid < r )
  Modify( rs( k ), l, r, d );
 return Up( k );
}
long long Query( int k, int pos )
{
 if( l( k ) == r( k ) )
  return ( mn( k ) <= a[ pos ] ) ? ( a[ pos ] - mn( k ) ) : ( a[ pos ] + ( INF - mn( k ) ) * 2 );
 Down( k );
 int mid = l( k ) + r( k ) >> 1;
 return pos <= mid ? Query( ls( k ), pos ) : Query( rs( k ), pos );
}
#undef l
#undef r
#undef mn
#undef tag
int main( )
{
 std::ios::sync_with_stdio( false );
 cin.tie( 0 );
 cout.tie( 0 );
 cin >> n >> q;
 For( i, 1, n )
  cin >> a[ i ];
 Build( 1, 1, n );
 int l, r, d;
 while( q-- )
 {
  cin >> ch >> l;
  if( ch == 'Q' )
   ANS += Query( 1, l );
  else
   cin >> r >> d, Modify( 1, l, r, d );
 }
 cout << ANS % MOD;
 return 0;
}