题目:http://codeforces.com/problemset/problem/356/A
题意:首先给你n,m,代表有n个人还有m次描述,下面m行,每行l,r,x,代表l到r这个区间都被x所击败了(l<=x<=r),被击败的人立马退出游戏让你最后输出每个人是被谁击败的,最后那个胜利者没被
人击败就输出0
思路:他的每次修改的是一个区间的被击败的人,他而且只会记录第一次那个被击败的人,用线段树堕落标记的话他会记录最后一次的,所以我们倒着来修改,
然后因为那个区间里面还包含了自己,在线段树操作里面修改不太方便,所以我们采用把他拆分成两个区间来操作
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct tree
{
int l,r;
int val;
}d[*];
struct sss
{
int x,y,z;
}a[];
int n,m;
void buildtree(int cnt,int l,int r)
{
if(cnt>n*) return;
d[cnt].l=l;
d[cnt].r=r;
int mid=(l+r)/;
buildtree(cnt*,l,mid);
buildtree(cnt*+,mid+,r);
}
void pushdown(int cnt)
{
if(d[cnt].val!=){
d[cnt*].val=d[cnt].val;
d[cnt*+].val=d[cnt].val;
d[cnt].val=;
}
}
void update(int cnt,int l,int r,int val){
if(l==d[cnt].l&&r==d[cnt].r){
d[cnt].val=val;
return;
}
pushdown(cnt);
int mid=(d[cnt].l+d[cnt].r)/;
if(r<=mid) update(cnt*,l,r,val);
else if(l>mid) update(cnt*+,l,r,val);
else{
update(cnt*,l,mid,val);
update(cnt*+,mid+,r,val);
} }
void query(int cnt,int x)
{
if(d[cnt].l==d[cnt].r){
if(d[cnt].val==x) printf("0 ");
else printf("%d ",d[cnt].val);
return;
}
pushdown(cnt);
int mid=(d[cnt].l+d[cnt].r)/;
if(x<=mid) query(cnt*,x);
else query(cnt*+,x); }
int main()
{
cin>>n>>m;
for(int i=;i<m;i++){
cin>>a[i].x>>a[i].y>>a[i].z;
}
buildtree(,,n);
for(int i=m-;i>=;i--){
if(a[i].z->=a[i].x) //拆分成两个区间来修改
update(,a[i].x,a[i].z-,a[i].z);
if(a[i].z+<=a[i].y)
update(,a[i].z+,a[i].y,a[i].z);
}
for(int i=;i<=n;i++){
query(,i);
}
}
Codeforces Round #207 (Div. 1) A. Knight Tournament (线段树离线)的更多相关文章
-
Codeforces Round #207 (Div. 1) A. Knight Tournament(STL)
脑子又卡了...来一发set的,STL真心不熟. #include <stdio.h> #include <string.h> #include <iostream> ...
-
Codeforces Round #603 (Div. 2) E. Editor(线段树)
链接: https://codeforces.com/contest/1263/problem/E 题意: The development of a text editor is a hard pro ...
-
Codeforces Round #244 (Div. 2) B. * Transfer 线段树rmq
B. * Transfer Time Limit: 20 Sec Memory Limit: 256 MB 题目连接 http://codeforces.com/problemset/pro ...
-
Codeforces Round #530 (Div. 2) F (树形dp+线段树)
F. Cookies 链接:http://codeforces.com/contest/1099/problem/F 题意: 给你一棵树,树上有n个节点,每个节点上有ai块饼干,在这个节点上的每块饼干 ...
-
Codeforces Round #546 (Div. 2) E 推公式 + 线段树
https://codeforces.com/contest/1136/problem/E 题意 给你一个有n个数字的a数组,一个有n-1个数字的k数组,两种操作: 1.将a[i]+x,假如a[i]+ ...
-
Codeforces Round #222 (Div. 1) D. Developing Game 线段树有效区间合并
D. Developing Game Pavel is going to make a game of his dream. However, he knows that he can't mak ...
-
Codeforces Round #275 Div.1 B Interesting Array --线段树
题意: 构造一个序列,满足m个形如:[l,r,c] 的条件. [l,r,c]表示[l,r]中的元素按位与(&)的和为c. 解法: 线段树维护,sum[rt]表示要满足到现在为止的条件时该子树的 ...
-
Codeforces Round #271 (Div. 2) F. Ant colony 线段树
F. Ant colony time limit per test 1 second memory limit per test 256 megabytes input standard input ...
-
Codeforces Round #406 (Div. 2) D. Legacy (线段树建图dij)
D. Legacy time limit per test 2 seconds memory limit per test 256 megabytes input standard input out ...
随机推荐
-
saltstack之(三)认证管理
salt-master和salt-minion之间需要进行认证,认证之后salt-master才能管理salt-minion. 1.在node1:[root@node1 ~]# egrep -v '^ ...
-
HANDLE HINSTANCE HWND CWnd CDC
HANDLE HINSTANCE HWND CWnd CDC 句柄: 柄,把柄 例如一个锅的手柄,你只要抓住了它,你就可以很好地操作那个锅,不过很明显你只能通过锅的手柄来做一些诸如炒菜之类的事,你 ...
-
CSU 1505	酷酷的单词 湖南省赛第十届题目
题目链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1505 题意:技巧题,就是一行字符串中,每个字母出现的次数互不相同,复即为酷的单词. 解题 ...
-
使用grunt压缩css是能否设置background-size不压缩进去呢?否则ie8不能识别
.index-bg{ background:url(img/index-bg-t.5344b19d.jpg) center center/cover no-repeat } 比如上面这样ie8不能识别 ...
-
[JBoss] JNDI与JBossNS
JNDI的作用 JNDI是 Java 命名与目录接口(Java Naming and Directory Interface). 随着分布式应用的发展,远程访问对象访问成为常用的方法.虽然说通过Soc ...
-
近期在调用 calendar.js 的时候出现中文乱码! 解决方式
近期写一个小项目的时候:在调用 calendar.js 的时候出现中文乱码! 如图所看到的: 原因在于: 我的jsp 页面,指定的是 UTF-8 编码,然而,调用的 calendar.js 的编码确 ...
-
cocos2d-x中使用JNI的调用JAVA方法
用cocos2d-x公布Android项目时.都应该知道要用JAVA与C/C++进行交互时会涉及到JNI的操作(Java Native Interface).JNI是JAVA的一个通用接口.旨在本地化 ...
-
CentOS 6.2 安装vsftpd 服务器(转)
CentOS 6.2 安装vsftpd 服务器 本人的CentOS 6.2是安装在win 2008 R2 server 的 Hyper-V 虚拟机中.centos使用光盘安装,以最小模式安装,完成后用 ...
-
LoadRunner常用方法
LR常用的函数 lr_start_transaction: 为性能分析标记事务的开始 lr_end_transaction: 为性能分析标记事务的结束 lr_rendezvous: 在 Vuser 脚 ...
-
LIGER UI GRID TREE解决打开子树的时候,母树图标全部变成+
1.为data增加Expanded.当打开时告知已打开 关闭时告知已关闭 2.修改ligergrid 如果是打开状态,则open