首先把破环难度之和看成数字，方块就是数字的二进制权值。
这样题目就转化为了若干个询问[l,r],然后对每个数字二进制位[l,r]位快速置零即求和操作
我们考虑建31棵线段树,每棵树维护他n个节点，表示n个数字的每一位二进制情况，每次清空暴力从低位向高位找[l,r]区间最先可以被清空的那一颗线段树，对其进行清空操作，询问时对31棵线段树[l,r]区间上按权值求和即可，然后你会不幸的发现超时了。
这里有个比较重要的性质没有用到: 对于每个数字，如果他的高位二进制被清空了,那么他的低位二进制一定也会被清空，
那么31棵树的31*n个懒标记其实有效的只有n个,31棵树也可以合并为一棵树操作
细节看代码
Solve by Segment Tree
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
struct Seg{
struct S{
int l,r;
int laz;
vector<int>data;
};
vector<S>tre;
int n;
Seg(int n):n(n),tre(n<<2){
build(1,n,1);
}
#define lc (p<<1)
#define rc (p<<1|1)
void pushup(int p){
for(int i=0;i<=30;i++) {
tre[p].data[i]=tre[lc].data[i]+tre[rc].data[i];
}
}
void pushdown(int p){
if(tre[lc].laz<tre[p].laz){
for(int i=tre[lc].laz;i<tre[p].laz;i++) tre[lc].data[i]=0;
tre[lc].laz=tre[p].laz;
}
if(tre[rc].laz<tre[p].laz){
for(int i=tre[rc].laz;i<tre[p].laz;i++) tre[rc].data[i]=0;
tre[rc].laz=tre[p].laz;
}
}
void build(int l,int r,int p){
tre[p]={l,r,0,vector<int>(31)};
if(l==r) return;
int mid=l+r>>1;
build(l,mid,lc);
build(mid+1,r,rc);
pushup(p);
}
void clear(int l,int r,int h,int p){//把0~h的高度全置零
if(tre[p].l>=l&&tre[p].r<=r){
for(int i=0;i<=h;i++) tre[p].data[i]=0;
if(tre[p].laz<h+1) tre[p].laz=h+1;
return;
}
pushdown(p);
int mid=tre[p].l+tre[p].r>>1;
if(l<=mid) clear(l,r,h,lc);
if(mid<r) clear(l,r,h,rc);
pushup(p);
}
void qry(int l,int r,vector<int>&res,int p){
if(tre[p].l>=l&&tre[p].r<=r){
for(int i=0;i<=30;i++) res[i]+=tre[p].data[i];
return;
}
pushdown(p);
int mid=tre[p].l+tre[p].r>>1;
if(l<=mid) qry(l,r,res,lc);
if(mid<r) qry(l,r,res,rc);
}
void Init_Leaf(int pos,ll val,int p){
if(tre[p].l==tre[p].r){
for(int i=0;i<=30;i++){
tre[p].data[i]=val%2;
val/=2;
}
return;
}
pushdown(p);
int mid=tre[p].l+tre[p].r>>1;
if(pos<=mid) Init_Leaf(pos,val,lc);
if(mid<pos) Init_Leaf(pos,val,rc);
pushup(p);
}
};
void solve(){
int n,q;
cin>>n>>q;
Seg S(n);
for(int i=1;i<=n;i++){
ll val;cin>>val;
S.Init_Leaf(i,val,1);
}
while(q--){
int op,l,r;
cin>>op>>l>>r;
vector<int>res(31);
S.qry(l,r,res,1);
if(op==2){
ll ans=0,T=1;
for(int i=0;i<=30;i++){
ans+=T*res[i];
T<<=1;
}
cout<<ans<<endl;
}
else{
int mn_h=-1;
for(int i=0;i<=30;i++){
if(res[i]>0) {
mn_h=i;
break;
}
}
if(mn_h!=-1) S.clear(l,r,mn_h,1);
}
}
}
int main(){
cin.tie(0)->ios::sync_with_stdio(false);
solve();
return 0;
}
其实线段树的区间修改对某一位是置零后就不会在进行第二次的，那么可以直接拿一个set搭配单点修改树状数组模拟解决
Solve by BIT&set
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
struct BIT{
vector<ll>a;
int n;
BIT(){}
BIT(int n):n(n){
a.resize(n+1);
}
void add(int x,ll k){
while(x<=n){
a[x]+=k;
x+=(x&-x);
}
}
ll qry(int x){
ll ans=0;
while(x){
ans+=a[x];
x&=x-1;
}
return ans;
}
ll qry(int l,int r){return qry(r)-qry(l-1);}
};
int n,q;ll x;
set<int>st[31];
inline void solve(){
cin>>n>>q;
BIT S(n+1);
for(int i=1;i<=n;i++) {
cin>>x;
S.add(i,x);
for(int j=0;j<=30;j++){
if(x>>j&1) st[j].insert(i);
}
}
while(q--){
int op,l,r;cin>>op>>l>>r;
if(op==1){
int mn_h=-1;
for(int i=0;i<=30;i++){
auto it=st[i].lower_bound(l);
if(it!=st[i].end()&&*it<=r){
mn_h=i;
break;
}
}
if(mn_h!=-1){
auto it=st[mn_h].lower_bound(l);
vector<int>to_erase;
while(it!=st[mn_h].end()&&*it<=r){
to_erase.push_back(*it);
++it;
}
for(int i:to_erase){
S.add(i,-(1LL<<mn_h));
st[mn_h].erase(i);
}
}
}
else{
cout<<S.qry(l,r)<<endl;
}
}
}
int main(){
cin.tie(0)->ios::sync_with_stdio(false);
solve();
return 0;
}
然后你会发现还是这样代码短了但是时间还是很吃紧，
如果把高位清除低位必定清楚看成一种依赖关系就可以考虑用并查集维护，
用 31 个并查集[
],分别维护高度 h 下的依赖关系
可以通过并查集缩短查找在某一位二进制权下比l大的第一个位置的时间
把查找位置的时间从
降到
Solve by BIT&DSU
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
struct BIT{
vector<ll>a;
int n;
BIT(){}
BIT(int n):n(n){
a.resize(n+1);
}
void add(int x,ll k){
while(x<=n){
a[x]+=k;
x+=(x&-x);
}
}
ll qry(int x){
ll ans=0;
while(x){
ans+=a[x];
x&=x-1;
}
return ans;
}
ll qry(int l,int r){return qry(r)-qry(l-1);}
};
struct DSU{
vector<int>f;
DSU(){}
DSU(int n){
f.resize(n+1);
iota(f.begin(),f.end(),0);
}
int find(int x){
return f[x]==x?x:f[x]=find(f[x]);
}
bool merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy){
return false;
}
f[fx]=fy;
return true;
}
bool same(int x,int y){return find(x)==find(y);}
};
int n,q,op,l,r;
inline void solve(){
cin>>n>>q;
BIT S(n+1);
vector<ll>a(n+1);
vector<DSU>dsu(31,DSU(n+2));
for(int i=1;i<=n;i++) {
cin>>a[i];
S.add(i,a[i]);
}
for(int i=0;i<=30;i++){
for(int j=1;j<=n;j++){
if(a[j]>>i&1^1) dsu[i].merge(j,j+1);;
}
}
while(q--){
cin>>op>>l>>r;
if(op==1){
int mn_h=-1;
for(int i=0;i<=30;i++){
int pos=dsu[i].find(l);
if(pos<=r){
mn_h=i;
break;
}
}
if(mn_h!=-1){
int pos=dsu[mn_h].find(l);
while(pos<=r){
S.add(pos,-(1LL<<mn_h));
dsu[mn_h].merge(pos,pos+1);
pos=dsu[mn_h].find(pos);
}
}
}
else cout<<S.qry(l,r)<<endl;
}
}
int main(){
cin.tie(0)->ios::sync_with_stdio(false);
solve();
return 0;
}
然后跑的就比较快了
感觉这场的题都挺有教育意义的,虽然我都不会
牛魔，赛时一个都没想到，糖了...
京公网安备 11010502036488号