Weed
duyege的电脑上面已经长草了，经过辨认上面有金坷垃的痕迹。
为了查出真相，duyege 准备修好电脑之后再进行一次金坷垃的模拟实验。
电脑上面有若干层金坷垃，每次只能在上面撒上一层高度为 vi 的金坷垃，或者除掉最 新 vi 层（不是量）撒的金坷垃。如果上面只留有不足 vi 层金坷垃，那么就相当于电脑上 面没有金坷垃了。
duyege 非常严谨，一开始先给你 m 个上述操作要你依次完成。然后又对实验步骤进行 了 q 次更改，每次更改都会改变其中一个操作为另外一个操作。每次修改之后都会询问最 终金坷垃的量有多少。
输入第一行为两个正整数 m、q，接下来 m 行每行 2 个整数 k、vi。k 为 0 时撒金坷垃， 为 1 时除金坷垃。接下来 q 行每行 3 个整数 ci、k、vi，ci 代表被更改的操作是第 ci 个， 后面 2 个数描述更改为这样的操作。 输出 q 行代表每次金坷垃的量为多少
对于 30%的数据，m<=1000,q<=1000.
对于另外 20%的数据，每次 k=1 时都会将金坷垃清空。
对于 100%的数据，m<=2*10^5,q<=2*10^5,vi<=10^4.
——————————————分割线——————————————
分析：
( 30分 )这道题朴素想法是每次对某个操作修改，然后依次算到最后一个元素。
( 100分 )朴素的想法在逐个计算上耗时太多，这时我们需要一种数据结构，能够对某个操作修改，又能够对某一段查询，那么不难想到线段树。
我们需要维护三个信息，即当前区间中操作的金坷垃数量，层数，以及需要删去更左边操作的层数。
显然左边的删除操作不会影响之后的操作，那么我们只需要对每个节点进行结算，统计即可。
下面代码的Push_up函数比较难懂，特此注释。
#include "bits/stdc++.h"
#define Never return
#define Explode 0 using namespace std ;
struct SegTree { int l , r , Add , Cnt , Del ;};
const int maxN = 2e5 + ; SegTree tr[ maxN << ] ;
int arr[ maxN ] ;
bool op[ maxN ] ; int INPUT ( ) {
int x = , f = ;char ch = getchar( ) ;
while ( ch < '' || ch > '' ) { if( ch == '-' ) f= - ; ch = getchar( ) ; }
while ( ch >= '' && ch <= '' ) { x = ( x << ) + ( x << ) + ch - '' ; ch = getchar( ) ; }
return x * f ;
} int Query_Tree ( const int i , const int Target ) {
if ( Target == tr[ i << | ].Add ) {
return tr[ i ].Cnt - tr[ i << | ].Cnt ;
}
else if ( Target < tr[ i << | ].Add ) {
return tr[ i ].Cnt - tr[ i << | ].Cnt + Query_Tree ( i << | , Target ) ;
}
else {
return Query_Tree ( i << , Target - tr[ i << | ].Add + tr[ i << | ].Del ) ;
}
} void Push_up ( const int i ) {
int lchild = i << ;
int rchild = lchild + ;
if ( tr[ rchild ].Del >= tr[ lchild ].Add ) {//右区间 删除数大于等于左边层数
tr[ i ].Del = tr[ lchild ].Del + tr[ rchild ].Del - tr[ lchild ].Add ;
tr[ i ].Add = tr[ rchild ].Add ;
tr[ i ].Cnt = tr[ rchild ].Cnt ;
}
else if ( !tr[ rchild ].Del ) {//右区间没有删除
tr[ i ].Add = tr[ lchild ].Add + tr[ rchild ].Add ;
tr[ i ].Cnt = tr[ lchild ].Cnt + tr[ rchild ].Cnt ;
tr[ i ].Del = tr[ lchild ].Del ;
}
else {//右边无法全部删去左边
tr[ i ].Del = tr[ lchild ].Del ;
tr[ i ].Add = tr[ lchild ].Add + tr[ rchild ].Add - tr[ rchild ].Del ;
tr[ i ].Cnt = tr[ rchild ].Cnt + Query_Tree ( lchild , tr[ rchild ].Del ) ;
}
}
void Build_Tree ( const int x , const int y , const int i ) {
tr[ i ].l = x ;
tr[ i ].r = y ;
if ( x == y ) {
if ( op[ x ] ) tr[ i ].Del = arr[ x ] ;
else if ( !op[ x ] ) {
tr[ i ].Add = ;
tr[ i ].Cnt = arr[ x ] ;
}
}
else {
int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
Build_Tree ( x , mid , i<< ) ;
Build_Tree ( mid + , y , i<<| ) ;
Push_up ( i ) ;
}
return ;
} void Update_Tree ( const int i , const int Target ) {
if ( tr[ i ].l == tr[ i ].r ) {
tr[ i ].Add = tr[ i ].Cnt = tr[ i ].Del = ;
if ( INPUT ( ) ) {
tr[ i ].Del = INPUT( ) ;
}
else {
tr[ i ].Cnt = INPUT ( ) ;
tr[ i ].Add = ;
}
}
else {
int mid = ( tr[ i ].l + tr[ i ].r ) >> ;
if ( Target > mid ) Update_Tree ( i << | , Target ) ;
else if( Target <= mid ) Update_Tree ( i << , Target ) ;
Push_up ( i ) ;
}
return ;
} int main ( ) {
int N , Q ;
freopen("weed.in", "r", stdin);
freopen("weed.out", "w", stdout);
scanf ( "%d%d" , &N , &Q ) ;
for ( int i= ; i<=N ; ++i ) scanf ("%d%d" , op + i , arr + i ) ;
Build_Tree ( , N , ) ;
while ( Q-- ) {
int tmp = INPUT ( ) ;
Update_Tree ( , tmp ) ;
printf ( "%d\n" , tr[ ].Cnt ) ;
}
fclose(stdin);
fclose(stdout);
Never Explode ;
}
Weed
NOIP_RP++;
2016-10-07 20:28:07
(完)