区间与或
前言
抽象模拟赛, 我现在菜的可怕
题面
疑似自出题, 反正不难, 就不找原题了
挂个 pdf
题目下载
算法
暴力
显然可以用线段树维护
观察到与运算和或运算的优先级不好处理, 考虑每一位分开处理(位运算常见处理方法)
如果是与运算, 一旦为 \(0\), 置为 \(0\)
如果是或运算, 只需要记录为 \(1\) 即可
代码显然非常好打, 于是略
但是这题卡常严重, 于是思考能不能用一个线段树解决
但是我不会
代码
upd : 伟大的常熟优化卡过去了, 来自伟大的 lhs
#include<bits/stdc++.h>
using namespace std;
struct Node {
int l, r, tag_xor, tag_y;
};
Node tree[4000010];
int a[4000010];
int n, m;
int KIll_ = (1ll<<32)-1;
char buf[1<<20],*p1,*p2;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
template<typename T>inline void read(T &x){
bool f=1;x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=!f;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=(f?x:-x);return;
}
template<typename T>inline void write(T x){
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');return;
}
inline void build(int l, int r, int index_) {
tree[index_].l = l;
tree[index_].r = r;
tree[index_].tag_y = KIll_;
if (l == r) {
return;
}
build(l, l + (r - l) / 2, index_ * 2);
build(l + (r - l) / 2 + 1, r, index_ * 2 + 1);
return;
}
inline void spread(int index_) {
int tg_xor = tree[index_].tag_xor;
int tg_y = tree[index_].tag_y;
tree[index_].tag_xor = 0;
tree[index_].tag_y = KIll_;
tree[index_ * 2].tag_y |= tg_xor;
tree[index_ * 2].tag_xor |= tg_xor;
tree[index_ * 2].tag_y &= tg_y;
tree[index_ * 2 + 1].tag_y |= tg_xor;
tree[index_ * 2 + 1].tag_xor |= tg_xor;
tree[index_ * 2 + 1].tag_y &= tg_y;
// clog<<"";
return;
}
inline void pls_xor(int l, int r, int index_, int num) {
if (l > r)return;
if (l == tree[index_].l && r == tree[index_].r) {
tree[index_].tag_y |= num;
tree[index_].tag_xor |= num;
// clog<<"";
return;
}
spread(index_);
pls_xor(l, min(r, tree[index_ * 2].r), index_ * 2, num);
pls_xor(max(l, tree[index_ * 2 + 1].l), r, index_ * 2 + 1, num);
return;
}
inline void pls_y(int l, int r, int index_, int num) {
if (l > r)return;
if (l == tree[index_].l && r == tree[index_].r) {
tree[index_].tag_y &= num;
return;
}
spread(index_);
pls_y(l, min(r, tree[index_ * 2].r), index_ * 2, num);
pls_y(max(l, tree[index_ * 2 + 1].l), r, index_ * 2 + 1, num);
return;
}
inline void get_all(int index_) {
if (tree[index_].l == tree[index_].r) {
a[tree[index_].l]=((0|tree[index_].tag_xor)&tree[index_].tag_y);
return;
}
spread(index_);
get_all(index_ * 2);
get_all(index_ * 2 + 1);
return;
}
const int Mod=1e9+7;
int main() {
// freopen("range.in","r",stdin);
// freopen("range.out","w",stdout);
read(n);read(m);
build(1, n, 1);
while (m--) {
int op, l, r, num;
read(op);read(l);read(r);read(num);
if (op == 2) {
pls_xor(l, r, 1, num);
} else {
pls_y(l, r, 1, num);
}
}
get_all(1);
long long ans=0;
for(int i=1;i<=n;i++){
ans+=1ll*a[i]*i;
ans%=Mod;
}
write(ans);
return 0;
}
正解
于是分析暴力的时间瓶颈, 显然处理了一些不必要的运算
对于每一位, 只需要考虑其最后一次操作
只要算法能跳过已经被修改的位置, 并且能记录哪些位置被修改, 即可
套路:
并查集
将 \(find(x)\) 设为在位置 \(x\) 后面的离 \(x\) 最近的没有操作过的位置，初始时 \(fa[x] = x\) ，当 \(x\) 被操作过之后我
们直接将 \(fa[x]\) 指向 \(x + 1\) 的位置，同时跳到 \(find(x + 1)\) 即可，那是我们下一个要进行修改的数。
具体的，我们每次从操作的左边界出发找下一个需要修改的数直到下一个需要修改的位置大于操作的右边
界
代码
由于并查集之前写过, 所以 ctj
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int n, m, f[1000010];
long long ans;
int find(int x)
{
if (f[x] == x)
return x;
return f[x] = find(f[x]);
}
struct node
{
int op, l, r, v;
} a[1000010];
signed main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d%d", &a[i].op, &a[i].l, &a[i].r, &a[i].v);
for (int j = 30; j >= 0; j--) // logn 枚举位数
{
for (int i = n; i >= 1; i--) // 初始化
f[i] = i;
for (int i = m; i >= 1; i--)
{
/*在从后到前的操作顺序下, 与操作只需要记录 0, 若其之后没有与运算 1, 那么答案显然为 0*/
if (a[i].op == 1) //与操作
{
if ((a[i].v & (1 << j)) == 0)
{
int pos = find(a[i].l); // 找到第一个未被操作的位置
while (pos <= a[i].r && pos)
{
f[pos] = find(pos + 1);
pos = f[pos];
}
}
}
else //或操作
{
if (a[i].v & (1 << j))
{
int pos = find(a[i].l);
while (pos <= a[i].r && pos)
{
ans += (1ll << j) * pos, ans %= mod;
f[pos] = find(pos + 1);
pos = f[pos];
}
}
}
}
}
printf("%lld\n", ans % mod);
return 0;
}
总结
多操作类型的题目, 应该想办法消除顺序的影响
当然之前连 线段树 2 都没做过, 没打出来可以理解
并查集可以处理操作的最后出现这一类问题
离线可以优化一类不强制在线问题, 因为其具有全局性