秋实大哥与战争

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

男儿何不带吴钩，收取关山五十州。

征战天下是秋实大哥一生的梦想，所以今天他又在练习一个对战游戏。

秋实大哥命令所有士兵从左到右排成了一行来抵挡敌人的攻击。

敌方每一次会攻击一个士兵，这个士兵就会阵亡，整个阵列就会从这个位置断开；同时有的时候已阵亡的士兵会受人赢气息感染而复活。

秋实大哥想知道某一时刻某一个士兵所在的阵列的长度是多少。

Input

第一行包含两个整数

接下来

0 x : 表示x位置的士兵受到攻击阵亡1 x : 表示x位置的士兵受人赢气息感染复活2 x : 秋实大哥想知道第x个士兵所在阵列的长度

Output

对于每一个

Sample input and output

Sample Input	Sample Output
5 32 20 32 2	52

Source

2015 UESTC Training for Data Structures

板子题；

#include<bits/stdc++.h>using namespace std;#define ll __int64#define mod 1000000007#define pi (4*atan(1.0))const int N=1e5+10,M=4e6+10,inf=1e9+10;struct is{    int l,r;    int lm,mm,rm;}tree[N<<2];void buildtree(int l,int r,int pos){    tree[pos].l=l;    tree[pos].r=r;    tree[pos].lm=tree[pos].rm=tree[pos].mm=(r-l+1);    if(l==r)    return;    int mid=(l+r)>>1;    buildtree(l,mid,pos<<1);    buildtree(mid+1,r,pos<<1|1);}void update(int point,int change,int pos){    if(tree[pos].l==point&&tree[pos].r==point)    {        tree[pos].lm=tree[pos].mm=tree[pos].rm=change;        return;    }    int mid=(tree[pos].l+tree[pos].r)>>1;    if(point<=mid)    update(point,change,pos<<1);    else    update(point,change,pos<<1|1);    tree[pos].mm=max(tree[pos<<1].mm,max(tree[pos<<1|1].mm,tree[pos<<1].rm+tree[pos<<1|1].lm));    tree[pos].rm=tree[pos<<1|1].rm;    tree[pos].lm=tree[pos<<1].lm;    if(tree[pos<<1|1].rm==tree[pos<<1|1].r-tree[pos<<1|1].l+1)    tree[pos].rm+=tree[pos<<1].rm;    if(tree[pos<<1].lm==tree[pos<<1].r-tree[pos<<1].l+1)    tree[pos].lm+=tree[pos<<1|1].lm;}int query(int x,int pos){    if(tree[pos].l==tree[pos].r||tree[pos].mm==0||tree[pos].mm==tree[pos].r-tree[pos].l+1)        return tree[pos].mm;    int mid=(tree[pos].r+tree[pos].l)>>1;    if(x<=mid)    {        if(x>=tree[pos<<1].r-tree[pos<<1].rm+1)        return query(x,pos<<1)+query(mid+1,pos<<1|1);        else        return query(x,pos<<1);    }    else    {        if(x<=tree[pos<<1|1].lm+tree[pos<<1|1].l-1)            return query(x,pos<<1|1)+query(mid,pos<<1);        else        return query(x,pos<<1|1);    }}int main(){    int x,y,z,i,t;    while(~scanf("%d%d",&x,&y))    {        buildtree(1,x,1);        while(y--)        {            int flag,x;            scanf("%d%d",&flag,&x);            if(flag==0||flag==1)            update(x,flag,1);            else            printf("%d\n",query(x,1));        }    }    return 0;}

UESTC 1061 秋实大哥与战争线段树区间合并

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > UESTC 1061 秋实大哥与战争 线段树区间合并

UESTC 1061 秋实大哥与战争 线段树区间合并