HU 1166:敵兵布陣(CDQ分治)

コンベヤー?ドア
単点修正、区間加算
クイズ:
もちろん、線分樹や樹状配列などのデータ構造は裸問題です.実はCDQ手法もあります.空間的に直接的にロゴを最適化します.
最初の区間の合計は、プレフィクスの合計に等しく、時間的にa＜b、シーケンス上のc＜dの二次元バイアス帯域の値を求めるものに変換される.あとは裸です.(逆順を求める対に相当します.)

#include
using namespace std;
const int Maxn=3e5+50;

streambuf *ib,*ob;
inline int read()
{
    char ch=ib->sbumpc();int i=0,f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=ib->sbumpc();}
    while(isdigit(ch)){i=(i<<1)+(i<<3)+ch-'0';ch=ib->sbumpc();}
    return i*f;
}
int buf[50];
inline void W(int x)
{
    if(!x){ob->sputc('0');return;}
    if(x<0){ob->sputc('-');x=-x;}
    while(x){buf[++buf[0]]=x%10,x/=10;}
    while(buf[0])ob->sputc(buf[buf[0]--]+'0');
    return;
}

int n,cnt,cnt2,ans[Maxn];
char ch[10];

struct query
{
    int pos,val,type;
}q[Maxn],tmp[Maxn];

inline void solve(int l,int r)
{
    if(l==r)return;
    int mid=(l+r)>>1;
    solve(l,mid);
    solve(mid+1,r);
    for(int i=l;i<=r;i++)tmp[i]=q[i];
    int head1=l,head2=mid+1,sum=0,pos=l;
    while(head1<=mid&&head2<=r)
    {
        if(tmp[head1].pos<=tmp[head2].pos)
        {
            if(tmp[head1].type==1)sum+=tmp[head1].val;
            q[pos++]=tmp[head1++];
        }
        else
        {
            if(tmp[head2].type!=1)ans[tmp[head2].val]+=((tmp[head2].type==2)?-1:1)*sum;
            q[pos++]=tmp[head2++];
        }
    }
    while(head1<=mid){q[pos++]=tmp[head1++];}
    while(head2<=r)
    {
        if(tmp[head2].type!=1)ans[tmp[head2].val]+=((tmp[head2].type==2)?-1:1)*sum;
        q[pos++]=tmp[head2++];
    }
}

int main()
{
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);ib=cin.rdbuf();
    ob = std::cout.rdbuf();
    int T=read();
    for(int tt=1;tt<=T;tt++)
    {
        cout<<"Case "<":"<<'
';
        memset(q,0,sizeof(q));memset(ans,0,sizeof(ans));
        n=read();cnt=cnt2=0;
        for(int i=1;i<=n;i++){q[++cnt].type=1;q[cnt].pos=i;q[cnt].val=read();}
        while(cin>>(ch+1),ch[1]!='E')
        {
            ++cnt;
            if(ch[1]=='A')
            {
                q[cnt].type=1;q[cnt].pos=read();q[cnt].val=read();
            }
            else if(ch[1]=='S')
            {
                q[cnt].type=1;q[cnt].pos=read();q[cnt].val=-read();
            }
            else
            {
                ++cnt2;q[cnt].type=2;q[cnt].pos=read()-1;q[cnt].val=cnt2;
                ++cnt;q[cnt].type=3;q[cnt].pos=read();q[cnt].val=cnt2;
            }
        }
        solve(1,cnt);
        for(int i=1;i<=cnt2;i++) {W(ans[i]),ob->sputc('
');}
    }
}