题解 P4969 【神秘的703】

WNico · 2019-07-04 16:01:32 · 题解

P4969 神秘的703

一道来自前辈的题目

推一下自己的Blog

当然啦顺手推一下现在的BookCity/4526(这是一个假的链接)

这个是之前用zkw写的。。（又是zkw）

除此之外就是和前辈一样的超出标记

总的来说就是这样

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define mx 500010
using namespace std;
typedef long long ll;
ll n,t,m,exa[mx],tmp;
ll tree[1048576];   
bool over[mx];  //超出标记

ll ans(int a,int b){
    if(a==b)  return -tree[a+n-1];
    ll bac=0;
    for(a+=n-1,b+=n-1;a^b^1;a>>=1,b>>=1){   //标准的求和
        if(a%2==0){
            bac+=tree[a^1];
        }
        if(b%2){
            bac+=tree[b^1];
        }
    }
    return bac;
}

void build(int i,int a){    //建树
    if(a>t) return;
    while(i) tree[i]++,i/=2;
}

void change(int i,int a){       //点变更
    while(i) tree[i]+=a,i/=2;
}

int main(){
    scanf("%lld%lld",&n,&t);ll p=n;n=pow(2,ceil(log2(n)));
    for(int i=1;i<=p;++i) cin>>exa[i];cin>>m;
    for(int i=n;i<n+p;++i) build(i,exa[i-n+1]);
    for(int ii=1;ii<=m;++ii){
        char ins[10];int a,b;
        scanf("%s%d%d",ins,&a,&b);
        switch(ins[0]){                 //指令
            case 'B':{
                exa[a]=exa[a]-b<=0?1:exa[a]-b;
                if(exa[a]<=t&&tree[a+n-1]==0&&!over[a]) change(a+n-1,1);
                break;
            }case 'G':{
                exa[a]*=b;
                if(exa[a]<=0) over[a]=1;
                if((exa[a]>t||over[a])&&tree[a+n-1]) change(a+n-1,-1);

            }case 'Z':{
                if(a>b) swap(a,b);
                printf("%lld\n",(ans(a,b)+tree[a+n-1]+tree[b+n-1])*600);
                break;
            }case 't':{
                exa[a]=b;over[a]=0;
                if(b<=t&&tree[a+n-1]==0) change(a+n-1,1);
                if(b>t&&tree[a+n-1]) change(a+n-1,-1);
                break;
            }
            default:{
                printf("err\n");        //错误代码
                break;
            }
        }
    }
    return 0;
}