kuangbin线段树专题(已更一半
啊。。这个专题才开的时候,学校就恢复了vj挂题的制度,加上各种比赛,以及文化课之类的,导致这个专题写的好慢。。。写完后也一直没时间总结博客。。就是懒…-------------------------------------------------------------------------
感觉…自己越来越没有斗志了…天天像个废物一样,就只会写几个傻瓜题,比赛也是签个到就开始罚坐。。学个新的图论算法几乎要自闭,,
图论也太难了吧!!!
图论也太难了吧!!!
图论也太难了吧!!!
二分图写着写着就遇到了HK算法,然后看不懂,,只会套板子,写着写着觉得放到暑假集训再处理这个二分图吧,不如先去把次小生成树完善一下,,然后写了四个题就遇到了最小树形图。。。再次自闭。。。。
还是先把这个线段树专题总结一下吧-------------------------------------------------------------------------
就三个题没补
一个是多重lazy标记。。写吐了。真不想写这个(不会。。
还有一个是扫描线处理周长问题(只学了处理面积,周长一时半会没看会。
最后一个就是很玄学的看都看不懂的题目。。说是三维线段树????
我太菜了…-------------------------------------------------------------
开始正文
专题链接
A - 敌兵布阵 HDU - 1166
单点修改 区间查询
最简单的线段树操作了,不如放个树状数组上来吧
int lowbit(int x){return x&(-x);}
int arr[maxn];
void updata(int pos,int val,int n){
while(pos<=n){
arr[pos]+=val;
pos+=lowbit(pos);
}
}
int query(int pos){
int ans=0;
while(pos>0){
ans+=arr[pos];
pos-=lowbit(pos);
}
return ans;
}
int cas=0;
void solve(){
ms(arr,0);
int n;cin>>n;
rep(i,1,n){
int tmp;cin>>tmp;
updata(i,tmp,n);
}
string ope;
int a,b;
cout<<"Case "<<++cas<<":"<<endl;
while(cin>>ope&&ope[0]!='E'){
cin>>a>>b;
if(ope[0]=='A'){
updata(a,b,n);
}else if(ope[0]=='S'){
updata(a,-b,n);
}else{
cout<<query(b)-query(a-1)<<endl;
}
}
}
B - I Hate It HDU - 1754
区间查询,单点更新
还是基本操作。。上题放树状数组,那这个就放线段树把
struct node{
int l,r;
int val;
}tree[maxn<<2];
void build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){
scanf("%d",&tree[rt].val);
return ;
}
build(lson);
build(rson);
tree[rt].val=max(tree[ls].val,tree[rs].val);
}
void updata(int rt,int a,int b){
int l=tree[rt].l,r=tree[rt].r;
if(l==r&&r==a){
tree[rt].val=b;
}else{
if(a<=md){
updata(ls,a,b);
}else{
updata(rs,a,b);
}
tree[rt].val=max(tree[ls].val,tree[rs].val);
}
}
int query(int rt,int a,int b){
int l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b){
return tree[rt].val;
}else{
if(b<=md){
return query(ls,a,b);
}else if(a>=md+1){
return query(rs,a,b);
}else{
return max(query(ls,a,md),query(rs,md+1,b));
}
}
}
void solve(){
int n,m;while(~scanf("%d %d",&n,&m)){
build(1,1,n);
while(m--){
char str[30];int a,b;
scanf("%s %d %d",str,&a,&b);
if(str[0]=='Q'){
cout<<query(1,a,b)<<endl;
}else{
updata(1,a,b);
}
}
}
}
C - A Simple Problem with Integers POJ - 3468
嗯。。区间更新,区间查询
考察的是lazy标记的思想,单点修改必定会超时的
算是lazy标记入门题
我想不明白的是。。用scanf就一直wa…改成cin…就过了
迷惑。。。
struct node{
ll l,r;
ll val,tag;
}tree[maxn<<2];
void build(ll rt,ll l,ll r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].tag=0;
if(l==r){
cin>>tree[rt].val;
}else{
build(lson);
build(rson);
tree[rt].val=tree[ls].val+tree[rs].val;
}
}
inline void push_down(ll rt){
if(!tree[rt].tag){
return ;
}
ll l=tree[rt].l,r=tree[rt].r;
tree[ls].tag+=tree[rt].tag;
tree[rs].tag+=tree[rt].tag;
tree[ls].val+=(md-l+1)*tree[rt].tag;
tree[rs].val+=(r-md)*tree[rt].tag;
tree[rt].tag=0;
}
void updata(ll rt,ll a,ll b,ll c){
ll l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b){
tree[rt].tag+=c;
tree[rt].val+=(r-l+1)*c;
return ;
}else{
push_down(rt);
if(b<=md){
updata(ls,a,b,c);
}else if(a>=md+1){
updata(rs,a,b,c);
}else{
updata(ls,a,md,c);
updata(rs,md+1,b,c);
}
tree[rt].val=tree[ls].val+tree[rs].val;
}
}
ll query(ll rt,ll a,ll b){
ll l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b){
return tree[rt].val;
}else{
push_down(rt);
if(b<=md){
return query(ls,a,b);
}else if(a>=md+1){
return query(rs,a,b);
}else{
return query(ls,a,md)+query(rs,md+1,b);
}
}
}
void solve(){
ll n,q;
cin>>n>>q;
build(1,1,n);
while(q--){
char ope[10];
ll a,b,c;
cin>>ope>>a>>b;
if(ope[0]=='Q'){
cout<<query(1,a,b)<<endl;
}else{
cin>>c;
updata(1,a,b,c);
}
}
}
D - Mayor’s posters POJ - 2528
呃。线段树染色+离散化处理
数据太大了,需要离散化一下,不然无法建树
注意这里每一个点代表的是片段的颜色,比如3,4,5,6,7
4,6之间,3,4之间,6,7之间依次染了色,然后你离散化就成了,3,4,6,7,对应1,2,3,4,然后你记录出来的就是1,2有颜色,3,4有颜色,这就忽略了一种颜色!!,原本的应该是,3,4 ,,,5,,6,7
所以离散化的时候,对于每一个长度大于1的区间,就需要额外添加一个数进去来确保正确度!即
for(ll i=1;i<=sz-1;i++){
if(v[i]-v[i-1]>1){
v.pb(v[i-1]+1);
}
}
注意这个题染的是点,和下面那个题不同,这点要区分开
然后就没啥好说的了,上代码吧,注意线段树离散化的操作
struct node{
ll l,r;
ll val;
}tree[maxn<<4];
struct IUPUT{
ll l,r;
}input[maxn];
ll vis[maxn<<4];
vector<ll>v;
ll ans=0;
void build(ll rt,ll l,ll r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].val=-1;
if(l==r){
return ;
}
build(lson);
build(rson);
}
inline void push_down(ll rt){
ll l=tree[rt].l,r=tree[rt].r;
if(tree[rt].val!=-1&&l!=r){
tree[ls].val=tree[rt].val;
tree[rs].val=tree[rt].val;
tree[rt].val=-1;
}
}
void updata(ll rt,ll a,ll b,ll c){
ll l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b){
tree[rt].val=c;
return ;
}
push_down(rt);
if(b<=md){
updata(ls,a,b,c);
}else if(a>=md+1){
updata(rs,a,b,c);
}else{
updata(ls,a,md,c);
updata(rs,md+1,b,c);
}
}
void query(ll rt,ll a,ll b){
ll l=tree[rt].l,r=tree[rt].r;
//de(tree[rt].val),de(l),de(r),de(a),de(b);
if(l==a&&r==b&&tree[rt].val!=-1){
ll tmp=tree[rt].val;
if(!vis[tmp]){
vis[tmp]=1;
ans++;
}
return ;
}
if(tree[rt].val==-1&&l==r){
return ;
}
push_down(rt);
if(b<=md){
query(ls,a,b);
}else if(a>=md+1){
query(rs,a,b);
}else{
query(ls,a,md);
query(rs,md+1,b);
}
}
void solve(){
v.clear();
ans=0;
ll n=read();
rep(i,1,n){
input[i].l=read();
input[i].r=read();
v.pb(input[i].l);
v.pb(input[i].r);
}
ll sz=v.size();
sort(v.begin(),v.end());
for(ll i=1;i<=sz-1;i++){
if(v[i]-v[i-1]>1){
v.pb(v[i-1]+1);
}
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
sz=v.size();
build(1,1,sz);
rep(i,1,n){
ll a=lower_bound(v.begin(),v.end(),input[i].l)-v.begin()+1;
ll b=lower_bound(v.begin(),v.end(),input[i].r)-v.begin()+1;
updata(1,a,b,i);
}
ms(vis,0);
query(1,1,sz);
cout<<ans<<endl;
}
E - Just a Hook HDU - 1698
就是个区间更新,区间查询的题目
题意:一个拐杖原本单位长度价值为1,然后每次选定一个,区间,把这个区间单位价值修改为 最后求区间之和。。
就是lazy的应用吧
struct node{
int l,r;
int val,tag;
}tree[maxn<<2];
void build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].tag=0;
if(l==r){
tree[rt].val=1;
return ;
}
build(lson);
build(rson);
tree[rt].val=tree[ls].val+tree[rs].val;
}
inline void push_down(int rt){
int l=tree[rt].l,r=tree[rt].r;
if(l==r||tree[rt].tag==0){
tree[rt].tag=0;
return ;
}
tree[ls].tag=tree[rs].tag=tree[rt].tag;
tree[ls].val=(md-l+1)*tree[ls].tag;
tree[rs].val=(r-md)*tree[rs].tag;
tree[rt].tag=0;
}
void updata(int rt,int a,int b,int c){
int l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b){
tree[rt].tag=c;
tree[rt].val=(r-l+1)*c;
return ;
}
push_down(rt);
if(b<=md){
updata(ls,a,b,c);
}else if(a>=md+1){
updata(rs,a,b,c);
}else{
updata(ls,a,md,c);
updata(rs,md+1,b,c);
}
tree[rt].val=tree[ls].val+tree[rs].val;
}
int query(int rt,int a,int b){
int l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b){
return tree[rt].val;
}
push_down(rt);
if(b<=md){
return query(ls,a,b);
}else if(a>=md+1){
return query(rs,a,b);
}else{
return query(ls,a,md)+query(rs,md+1,b);
}
}
int cas=0;
void solve(){
int n=read();build(1,1,n);
int q=read();while(q--){
int a=read(),b=read(),c=read();
updata(1,a,b,c);
}
printf("Case %d: The total value of the hook is %d.\n",++cas,query(1,1,n));
}
F - Count the Colors ZOJ - 1610
也是线段树染色问题,每次把一个区域染成颜色,最后求出每种颜色有多少段,输出段数,为0(或者被覆盖完)则不用输出
因为这个染色的是线段,不是点,也即是说【1,2】 和【3,4】是不相邻的
这时候我们可以用来代替到这个区间,更新数值的时候更新
L+1,R的点就可以了,最后暴力找出每个颜色的段数
struct segtree{
int l,r;
int val;
}tree[maxn<<2];
int vis[maxn],ans,cup[maxn];
void build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].val=-1;
if(l==r){
return ;
}
build(lson);
build(rson);
}
inline void push_down(int rt){
int l=tree[rt].l,r=tree[rt].r;
if(l==r||tree[rt].val==-1){
return ;
}
tree[ls].val=tree[rs].val=tree[rt].val;
tree[rt].val=-1;
}
void updata(int rt,int a,int b,int c){
//de(l),de(r);
//de(rt);
int l=tree[rt].l,r=tree[rt].r;
//de(a),de(b),de(l),de(r);
if(l==a&&r==b){
tree[rt].val=c;
return ;
}
push_down(rt);
if(b<=md){
updata(ls,a,b,c);
}else if(a>=md+1){
updata(rs,a,b,c);
}else{
updata(ls,a,md,c);
updata(rs,md+1,b,c);
}
}
void query(int rt,int a,int b){
int l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b&&tree[rt].val!=-1){
for(int i=l;i<=r;i++){
cup[i]=tree[rt].val;
}
return ;
}
if(l==r&&tree[rt].val!=-1){
return ;
}
push_down(rt);
if(b<=md){
query(ls,a,b);
}else if(a>=md+1){
query(rs,a,b);
}else{
query(ls,a,md);
query(rs,md+1,b);
}
}
void solve(){
int n;while(~scanf("%d",&n)){
int N=8001;
build(1,1,N-1);
ms(vis,0),ms(cup,-1);
rep(i,1,n){
int x1,x2,c;
scanf("%d %d %d",&x1,&x2,&c);
x1++;
updata(1,x1,x2,c);
}
query(1,1,N-1);
for(int i=1;i<=N;i++){
if(cup[i-1]!=-1&&(i==1||cup[i-1]!=cup[i-2])){
vis[cup[i-1]]++;
}
}
for(int i=0;i<=N;i++){
if(vis[i]){
printf("%d %d\n",i,vis[i]);
}
}
printf("\n");
}
}
G - Balanced Lineup POJ - 3264
呃,区间最值查询,每次输出一个区间最大值与最小值的差值
简单题》。
struct segtree{
int l,r;
int mx,mn;
}tree[maxn<<2];
int ans1,ans2;
void build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
if(l==r){
int tmp=read();
tree[rt].mx=tree[rt].mn=tmp;
return ;
}
build(lson);
build(rson);
tree[rt].mx=max(tree[ls].mx,tree[rs].mx);
tree[rt].mn=min(tree[ls].mn,tree[rs].mn);
}
void query(int rt,int a,int b){
int l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b){
ans1=max(ans1,tree[rt].mx);
ans2=min(ans2,tree[rt].mn);
return ;
}
if(b<=md){
query(ls,a,b);
}else if(a>=md+1){
query(rs,a,b);
}else{
query(ls,a,md);
query(rs,md+1,b);
}
}
void solve(){
int n=read(),q=read();
build(1,1,n);
while(q--){
int a=read(),b=read();
ans1=-1*INF;
ans2=INF;
query(1,a,b);
printf("%d\n",ans1-ans2);
}
}
H - Can you answer these queries? HDU - 4027
区间更新,区间求和
由于这个区间更新是开方操作。。。所以必然不能用lazy标记了。。
但是暴力会超时?那怎么办
仔细想想,开方操作对于一个整数来说,最多操作6,7次就变成1了,变成1之后的开方就不会再变化了,所以我们还是暴力更新。只不过需要维护一下每个区间是否全为1了,是的话就不需要更新了,区间求和就是常规套路了
struct segtree{
ll l,r;
ll val,be;
}tree[maxn<<2];
void build(int rt,int l,int r){
tree[rt].l=l;
tree[rt].r=r;
tree[rt].be=0;
if(l==r){
scanf("%lld",&tree[rt].val);
if(tree[rt].val==1){
tree[rt].be=1;
}
return ;
}
build(lson);
build(rson);
tree[rt].val=tree[ls].val+tree[rs].val;
tree[rt].be= tree[rt].val==(r-l+1);
}
void updata(ll rt,ll a,ll b){
ll l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b&&tree[rt].be==1){
return ;
}
if(l==a&&l==r){
tree[rt].val=sqrt(tree[rt].val);
}else if(b<=md){
updata(ls,a,b);
}else if(a>=md+1){
updata(rs,a,b);
}else{
updata(ls,a,md);
updata(rs,md+1,b);
}
if(l != r){
tree[rt].val=tree[ls].val+tree[rs].val;
}
tree[rt].be = tree[rt].val==(r-l+1);
}
ll query(ll rt,ll a,ll b){
ll l=tree[rt].l,r=tree[rt].r;
if(l==a&&r==b){
return tree[rt].val;
} else {
if (b <= md) {
return query(ls,a,b);
} else if (a >= md+1){
return query(rs,a,b);
} else {
return query(ls,a,md) + query(rs,md+1,b);
}
}
}
void solve(){
ll cas=0;
ll n;while(~scanf("%lld",&n)){
build(1,1,n);
ll m;scanf("%lld",&m);
printf("Case #%lld:\n",++cas);
while(m--){
ll a,b,c;scanf("%lld %lld %lld",&a,&b,&c);
if(b>c){
swap(b,c);
}
if (a==0) {
updata(1,b,c);
} else {
printf("%lld\n",query(1,b,c));
}
}
puts("");
}
}
先鸽了…明后天再继续补
上一篇: Kuangbin专题八生成树
下一篇: MySql 5.7 windows 安装