2018湘潭大学程序设计竞赛【H】
2024-09-06 05:58:48
题目链接:https://www.nowcoder.com/acm/contest/105/H
题意:两个操作,一个在[l,r]区间放颜色为c的球,一个统计在[l,r]里有多少不同颜色的球。
题解:哎,线段树嘛。板子嘛、把求和操作改一改嘛。当时没用lazy操作T了嘛。谢谢大佬的板子。小萌新知道lazy是个啥玩意儿了。emmm..最后统计一下1的个数就是答案啦。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
struct data{
int l,r;
ll add;
ll sum;
}data[]; void build(int l,int r,int k){
data[k].l=l;
data[k].r=r;
data[k].add=;
data[k].sum=;
if(l==r){
return ;
}
int mid=(data[k].l+data[k].r) >> ;
build(l,mid,k*);
build(mid+,r,k*+);
} void pushdown(int k){
if(data[k].add==) return ;
data[k*].sum |= data[k].add;
data[k*+].sum |= data[k].add;
data[k*].add |= data[k].add;
data[k*+].add |=data[k].add;
data[k].add=;
} void update(int l,int r,int x,int k){
if(data[k].l==l&&data[k].r==r){
data[k].sum|=(ll)(1LL<<x);
data[k].add|=(ll)(1LL<<x);
return ;
}
pushdown(k);
int mid=(data[k].l + data[k].r)/;
if(r <= mid){
update(l,r,x,k*);
}else if(l > mid){
update(l,r,x,k*+);
}else{
update(l,mid,x,k*);
update(mid+,r,x,k*+);
}
data[k].sum=data[k*].sum | data[k*+].sum;
} ll query(int l,int r,int k){
if(data[k].l==l&&data[k].r==r){
return data[k].sum;
}
pushdown(k);
int mid=(data[k].l + data[k].r) / ;
if(r <= mid){
return query(l,r,k*);
}else if(l > mid){
return query(l,r,k*+);
}else{
return query(l,mid,k*) | query(mid+,r,k*+);
}
} int main(){
int n,m;
scanf("%d %d",&n,&m);
build(,n,);
while(m--){
int flag;
scanf("%d",&flag);
if(flag==){
int x,y,k;
scanf("%d%d%d",&x,&y,&k);
update(x,y,k,);
}else{
int x,y;
scanf("%d%d",&x,&y);
int ans = query(x,y,);
int cnt = ;
while(ans){
if(ans&)
cnt++;
ans = ans >> ;
}
cout<<cnt<<endl;
}
}
return ;
}
最新文章
- 基本组件的使用&mdash;&mdash;UINavigationController
- 【转】你所不知道的Android Studio调试技巧
- 常用备份工具是mysql自带的mysqldump
- iOS开发--二维码的生成
- redis配置详情
- OOD原则汇总
- Sonar相关资料
- Java程序设计的基本原则
- C#:控制台程序调用中间库创建窗体
- Mybatis学习(叁)
- PhoneGap + Dreamweaver 5.5 无法在模拟器中打开的问题(二)
- OSSchedLock()函数透析
- jQuery中两种阻止事件冒泡的区别
- 设计模式(7)--Bridge(桥接模式)--结构型
- hdu_2669 Romantic(扩展欧几里得)
- Ubuntu 16.04安装JDK(转载)
- Exception in thread ";main"; java.util.InputMismatchException
- [hive] hiveql 基础操作
- 【设计模式】用追MM来解释23种设计模式,转
- MySQL查询性能调优化