洛谷P5522 【[yLOI2019] 棠梨煎雪】
2024-08-26 16:10:08
区间操作考虑用线段树维护。
建\(n*2\)棵线段树，前\(n\)棵线段树维护每个串的第i位是否是0。
后\(n\)棵线段树维护每个串的第i位是否是1。
如果是问号的话，直接跳过就好(通过1和0能看出是否是问号)。
然后分三种情况统计答案：
1.有1也有0,不可能，\(ans=0\)
2.只有1或0，一种情况，\(ans\)不变。
3.既没有0也没有1，两种情况\(ans*=2\)
像这样这棵线段树。
但是这样会很慢。
考虑状压。
这样只用开两棵线段树，一个存零，一个存一。
把状态压缩成一个\(int\),最多30位，转换成十进制\(int\)能存下。
然后的建树、查询、更改操作其实就是类似一个模板。
建树：
void build(int hao,int l,int r)
{
if(l==r)
{
for(int i=1;i<=n;i++)
{
if(s[l][i]=='?')//问号跳过
{
continue;
}
flag[hao][s[l][i]-'0']|=(1<<(i-1));//状压
}
return;
}
int mid=(l+r)/2;
build(hao<<1,l,mid);
build(hao<<1|1,mid+1,r);
flag[hao][0]=flag[hao<<1][0]|flag[hao<<1|1][0];
flag[hao][1]=flag[hao<<1][1]|flag[hao<<1|1][1];
}
查询：
data query(int hao,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
return (data){flag[hao][0],flag[hao][1]};
}
int mid=(l+r)/2;
data kkk=none;
if(L<=mid)
{
kkk=kkk+query(hao<<1,l,mid,L,R);
}
if(R>mid)
{
kkk=kkk+query(hao<<1|1,mid+1,r,L,R);
}
return kkk;
}
我们这里返回一个data的量，以便于后面计算答案。
计算答案的主程序：
scanf("%d%d",&l,&r);
data ans=query(1,1,m,l,r);
anss=1;
for(int i=1;i<=n;i++)//只有1或0的方案数只有一种
{
if(ans.x&1&&ans.y&1)//第i位既有1又有0，不可能。
{
anss=0;
break;
}
if(!(ans.x&1)&&!(ans.y&1))//都是问号
{
anss*=2;
}
ans.x>>=1;
ans.y>>=1;
}
ansss^=anss;
更改：
void change(int hao,int l,int r,int x)
{
if(l==r)
{
flag[hao][0]=flag[hao][1]=0;//单点修改
for(int i=1;i<=n;i++)
{
if(ch[i]=='?')
{
continue;
}
flag[hao][ch[i]-'0']|=(1<<(i-1));
}
return;
}
int mid=(l+r)/2;
if(x<=mid)
{
change(hao<<1,l,mid,x);
}else{
change(hao<<1|1,mid+1,r,x);
}
flag[hao][0]=flag[hao<<1][0]|flag[hao<<1|1][0];
flag[hao][1]=flag[hao<<1][1]|flag[hao<<1|1][1];
}
最后就把这些函数结合在一起就可以了。
#include<bits/stdc++.h>
#define N 400010
using namespace std;
int flag[N<<2][2],n,m,q,op,ansss,l,r,anss;
char s[N][41],ch[41];
struct data
{
int x,y;
}none;
data operator +(data a,data b)
{
return (data){a.x|b.x,a.y|b.y};
}
void build(int hao,int l,int r)
{
if(l==r)
{
for(int i=1;i<=n;i++)
{
if(s[l][i]=='?')//问号跳过
{
continue;
}
flag[hao][s[l][i]-'0']|=(1<<(i-1));//状压
}
return;
}
int mid=(l+r)/2;
build(hao<<1,l,mid);
build(hao<<1|1,mid+1,r);
flag[hao][0]=flag[hao<<1][0]|flag[hao<<1|1][0];
flag[hao][1]=flag[hao<<1][1]|flag[hao<<1|1][1];
}
data query(int hao,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
return (data){flag[hao][0],flag[hao][1]};
}
int mid=(l+r)/2;
data kkk=none;
if(L<=mid)
{
kkk=kkk+query(hao<<1,l,mid,L,R);
}
if(R>mid)
{
kkk=kkk+query(hao<<1|1,mid+1,r,L,R);
}
return kkk;
}
void change(int hao,int l,int r,int x)
{
if(l==r)
{
flag[hao][0]=flag[hao][1]=0;//单点修改
for(int i=1;i<=n;i++)
{
if(ch[i]=='?')
{
continue;
}
flag[hao][ch[i]-'0']|=(1<<(i-1));
}
return;
}
int mid=(l+r)/2;
if(x<=mid)
{
change(hao<<1,l,mid,x);
}else{
change(hao<<1|1,mid+1,r,x);
}
flag[hao][0]=flag[hao<<1][0]|flag[hao<<1|1][0];
flag[hao][1]=flag[hao<<1][1]|flag[hao<<1|1][1];
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++)
{
scanf("%s",s[i]+1);
}
build(1,1,m);
for(int i=1;i<=q;i++)
{
scanf("%d",&op);
if(op==0)
{
scanf("%d%d",&l,&r);
data ans=query(1,1,m,l,r);
anss=1;
for(int i=1;i<=n;i++)//只有1或0的方案数只有一种
{
if(ans.x&1&&ans.y&1)//第i位既有1又有0，不可能。
{
anss=0;
break;
}
if(!(ans.x&1)&&!(ans.y&1))//都是问号
{
anss*=2;
}
ans.x>>=1;
ans.y>>=1;
}
ansss^=anss;
}else{
scanf("%d%s",&l,ch+1);
change(1,1,m,l);
}
}
printf("%d\n",ansss);
return 0;
}
最新文章
- 我的LESS编译方案
- C#根据句柄改变窗体控件值
- Java字符串面试（二）
- 对“Java”的诞生历史、特点、定义等HR常问的简单题
- Java多线程之新类库中的构件CountDownLatch
- C++primer 练习15.26
- Demo学习： ColumnSort
- [渣译文] SignalR 2.0 系列： SignalR 自托管主机
- JVM学习（1）——通过实例总结Java虚拟机的运行机制-转载http://www.cnblogs.com/kubixuesheng/p/5199200.html
- 【转】JAVA处理线程超时
- 【BZOJ3531】旅行（树链剖分，线段树）
- 关于HTTP协议学习（二）
- Mac安装LNMP环境，升级php7
- SVN问题之——org.apache.subversion.javahl.ClientException: Attempted to lock an already-locked dir(网摘文)
- jquery multi-select 实例demo
- solr学习三（测试类，含普通与ExtractingRequestHandler测试）
- java 判断字符串是否相等
- 线段树【p1607】[USACO09FEB]庙会班车Fair Shuttle
- 【线性基】bzoj2322: [BeiJing2011]梦想封印
- 7、html的body内标签之图片及表格