BZOJ 2223 [Coci 2009]PATULJCI 主席树

2024-03-30 16:58
文章标签 bzoj 2009 主席 coci 2223 patuljci

本文主要是介绍BZOJ 2223 [Coci 2009]PATULJCI 主席树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

Input

Output

10 3 1 2 1 2 1 2 3 2 3 3 8 1 2 1 3 1 4 1 5 2 5 2 6 6 9 7 10

Sample Input

no
yes 1
no
yes 1
no
yes 2
no
yes 3

Sample Output

HINT

Notice:输入第二个整数是序列中权值的范围Lim,即1<=ai(1<=i<=n)<=Lim。

1<=Lim<=10000




传送门

同bzoj3524~~~

完全一样的题= =

我连数据范围都没改就交了……

注意一下输出的格式两题是不同的。



#include<bits/stdc++.h>
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int N=500005,logN=25;
int n,LIM,Tcnt;
int root[N];
struct ChairTree{int l,r,num;
}ct[N*logN];
void insert(int L,int R,int &x,int val){ct[Tcnt++]=ct[x];x=Tcnt-1;ct[x].num++;if (L==R) return;int mid=(L+R)>>1;if (val<=mid) insert(L,mid,ct[x].l,val);else insert(mid+1,R,ct[x].r,val);
}
int query(int L,int R,int ll,int rr,int g){if (L==R) return L;int mid=(L+R)>>1,t1=ct[ct[rr].l].num-ct[ct[ll].l].num,t2=ct[ct[rr].r].num-ct[ct[ll].r].num;if (t1>g) return query(L,mid,ct[ll].l,ct[rr].l,g); elseif (t2>g) return query(mid+1,R,ct[ll].r,ct[rr].r,g);else return 0;
}
int main(){n=read(),LIM=read();root[0]=0,Tcnt=1;for (int i=1;i<=n;i++)root[i]=root[i-1],insert(1,LIM,root[i],read());int x,y,m=read();while (m--){x=read(),y=read();int t=query(1,LIM,root[x-1],root[y],(y-x+1)>>1);if (!t) puts("no");else printf("yes %d\n",t);}return 0;
}

这篇关于BZOJ 2223 [Coci 2009]PATULJCI 主席树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/862055

相关文章

【系统架构设计师-2009年】综合知识-答案及详解

更多内容请见: 备考系统架构设计师-核心总结索引 文章目录 【第1题】【第2~4题】【第5题】【第6题】【第7~8题】【第9~10题】【第11题】【第12题】【第13题】【第14题】【第15题】【第16题】【第17题】【第18题】【第19题】【第20题】【第21题】【第22题】【第23题】【第24题】【第25~26题】【第27~28题】【第29~30题】【第31题】【第32~33题】

【POJ】2104 K-th Number 静态第K小——主席树

传送门:【POJ】2104 K-th Number 题目分析: 哇咔咔,又get了一个新技能——主席树,初步学习主席树,一次AC,感觉好棒~ 也在此Orz一下发明者主席——fotile96,在叉姐群经常看到主席的身影,不过蒟蒻也只能仰望神犇的背影了,起步迟且天赋不如人,只能慢慢的走下去,希望有一天能看到另一个世界。 主席树的编程方式是函数式编程(可持久化),保证我们可以查询历史

【BZOJ】1324 Exca王者之剑 最大权独立集

传送门:【BZOJ】1324  Exca王者之剑 题目分析:赤裸裸的最大权独立集。。。最小割解决 代码如下: #include <cstdio>#include <vector>#include <cstring>#include <algorithm>using namespace std ;#define REP( i , a , b ) for ( int

【BZOJ】1026: [SCOI2009]windy数 数位DP

传送门:【BZOJ】1026: [SCOI2009]windy数 题目分析:数位DP水题。 代码如下: #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,

【BZOJ】2152: 聪聪可可 点分治

传送门:【BZOJ】2152: 聪聪可可 题目分析:记录权值和%3的路径的个数。。。然后去重。。没了。。 代码如下: #include <vector>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std ;typedef lo

九度考研真题 浙大 2009-1浙大1031:xxx定律

//1031:xxx定律 #include<iostream> using namespace std; int main(){ int n; while(cin>>n&&n!=0){ int num=0; while(n!=1){ if(n%2==0){ n/=2; num++; } else{ n=3*n+1; n/

BZOJ 2440 2301 莫比乌斯应用

http://www.lydsy.com/JudgeOnline/problem.php?id=2440 Description 小 X 自幼就很喜欢数。但奇怪的是,他十分讨厌完全平方数。他觉得这些 数看起来很令人难受。由此,他也讨厌所有是完全平方数的正整数倍的数。然而 这丝毫不影响他对其他数的热爱。  这天是小X的生日,小 W 想送一个数给他作为生日礼物。当然他不能送一 个小X讨厌

BZOJ 3732: Network(最小生成树+倍增)

题目链接 题意:给出一个图,每个询问的格式是:A B,表示询问从A点走到B点的所有路径中,最长的边最小值是多少 很明显最终查询的边一定是在最小生成树里面的,先跑出最小生成树,然后,可以树链剖分,也可以使用倍增来计算 #include<bits/stdc++.h>using namespace std;#define cl(a,b) memset(a,b,sizeof(a))#define

腾讯公司后台服务器经典面试题 (2009年5月)

转自http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=1484141&page=1 前些时间去了腾讯面试, 可惜现场没回答好。 是一些基础问题,同时也比较深入的问题。 在此列出来, 欢迎大家讨论交流。 提问(不按时间顺序): 1, 使用Linux epoll模型,水平触发模式(Level-Triggered);当socket可写

杭电 acm 2009

求数列的和 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 42988    Accepted Submission(s): 26574 Problem Description 数列的定义如