LDUOJ 时间锁链（状压+线段树）

Kitty ·

更新时间:2024-11-10

· 873 次阅读

时间锁链

时间限制: 1 Sec 内存限制: 128 MB
[命题人:admin] [ Edit] [ TestData]
题目描述
当墨老师找到封闭时间环中最小的逆序对数后，他就可以将时间环展开成一个长L的时间锁链（我们可以将之看成是一根很长的管子），其中L是整数，所以我们可以将该管子分为L段，并从左到右标记为1，2，…，L。

现在对管子有两种操作：

“C A B C” 将A到B的数都标记为C（我们可形象的看成是染成C这种颜色）。

“P A B” 输出A和B之间不同颜色的数目。

颜色有T种，标记为1，2，3…，T，T是一个很小的值，初始时管子的颜色为1。
输入
第一行为L (1≤L≤100 000)，T (1≤T≤30)和O (1≤O≤100 000)，其中O表示操作数。随后O行为操作命令即"C A B C"或"P A B"，其中A可能比B值大。
输出
输出操作的结果。
样例输入 Copy
2 2 4
C 1 1 2
P 1 2
C 2 2 2
P 1 2
样例输出 Copy
2
1

题意：
题意很简单，给你一个区间和两种操作，你可以更改区间的数或是查询区间里有多少种不同的数。
思路：
典型的区间修改和区间查询，用线段树维护一下就可以了。
因为颜色的总数目很小，我们可以开一个bool数组暴力记录（应该可以~），也可以把状态压缩成二进制数，表示的含义就是第i位为1时说明第i个颜色被涂上了。

代码：
注意一下pushdown的写法~

#include
using namespace std;
typedef long long ll;
const int maxn=1e6+7;
struct node{
    int l,r;
    int sum;//二进制表示涂了多少种颜色
    int lazy;
}a[maxn];
void pushdown(int u){
    if(a[u].lazy){
        a[u<<1].lazy=a[u<<1|1].lazy=a[u].lazy;
        a[u<<1].sum=a[u<<1|1].sum=(1<<a[u].lazy);
        a[u].lazy=0;
    }
}
void build(int u,int l,int r){
    a[u].l=l;a[u].r=r;
    if(l==r) a[u].sum=1<>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        a[u].sum=a[u<<1].sum|a[u<r||a[u].r=l&&a[u].r<=r){//完全包含
        a[u].sum=1<<z;
        a[u].lazy=z;
        return ;
    }
    pushdown(u);
    update(u<<1,z,l,r);update(u<<1|1,z,l,r);
    a[u].sum=a[u<<1].sum|a[u<r||a[u].r=l&&a[u].r<=r) return a[u].sum;
    pushdown(u);
    return query(u<<1,l,r)|query(u<>n>>t>>o;
    build(1,1,n);
    while(o--){
        char op;int x,y;
        cin>>op>>x>>y;
        if(op=='P'){
            if(x>y) swap(x,y);
            int res=query(1,x,y);
            int sum=0;
            for(int i=1;i<=t;i++)
                if(res&(1<<i)) sum++;
            cout<<sum<y) swap(x,y);
            cin>>z;
            update(1,z,x,y);
        }
    }
    return 0;
}

作者：豆沙呀

线段树

1024 个赞