codeforces 482B. Interesting Array【線段樹區間更新】
來源：程序員人生 發布時間：2014-11-17 08:27:45 閱讀次數：1959次
題目：codeforces 482B. Interesting Array
題意：給你1個值n和m中操作，每種操作就是3個數 l ，r，val。就是區間l---r上的與的值為val，最后問你原來的數組是多少？如果不存在輸出no
分析：分析發現要滿足所有的區間，而1個點上假設有多個區間的話，這個點的值就是所有區間或的值，由于只有這樣才能滿足所有區間的，把所有位上的1都保存下來了，那末可以發現用線段樹來保護，但是那末怎樣判斷滿不滿足條件呢？可以也用線段樹，更新了以后在全部保護1遍看看滿不滿足題意，如果滿足的話就能夠了。
AC代碼：
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 110000;
struct Node
{
int l,r;
int val;
};
Node tree[10*N];
void build(int o,int l,int r)
{
tree[o].l = l,tree[o].r = r;
tree[o].val = 0;
if(l==r)
return ;
int mid = (l+r)/2;
build(o+o,l,mid);
build(o+o+1,mid+1,r);
}
void update(int o,int l,int r,int val)
{
if(tree[o].l==l && tree[o].r==r)
{
tree[o].val|=val;
return ;
}
int mid = (tree[o].l + tree[o].r)/2;
if(mid>=r)
update(o+o,l,r,val);
else if(l>mid)
update(o+o+1,l,r,val);
else
{
update(o+o,l,mid,val);
update(o+o+1,mid+1,r,val);
}
}
int query(int o,int l,int r)
{
if(tree[o].l==l && tree[o].r==r)
return tree[o].val;
int mid = (tree[o].l + tree[o].r)/2;
if(mid>=r)
return query(o+o,l,r);
else if(l>mid)
return query(o+o+1,l,r);
else
{
return query(o+o,l,mid)&query(o+o+1,mid+1,r);
}
}
vector<int> ans;
void solve(int o)
{
if(o!=1)
tree[o].val |= tree[o/2].val;
//printf("%d %d %d %d
",o,tree[o].l,tree[o].r,tree[o].val);
if(tree[o].l==tree[o].r){
ans.push_back(tree[o].val);
return ;
}
solve(o+o);
solve(o+o+1);
}
Node a[N];
int main()
{
//freopen("Input.txt","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].val);
update(1,a[i].l,a[i].r,a[i].val);
}
int ok=1;
for(int i=0;i<m;i++)
{
if(query(1,a[i].l,a[i].r)!=a[i].val)
{
ok=0;
break;
}
}
solve(1);
if(ok){
puts("YES");
for(int i=0;i<ans.size();i++)
printf("%d%c",ans[i],i==n?'
':' ');
ans.clear();
}
else
puts("NO");
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
