4
20
2016
1

[bzoj]1056&1862: [HAOI2008]排名系统

这不是裸题吗?干嘛拿出来,太闲?

是是是,您教导的是

主要促使我写这题的动力是:怎么他们写的都是$splay$和$treap$?

Category: bzoj | Tags: hash 平衡树 线段树
4
18
2016
0

[bzoj]3637: Query on a tree VI

传送门-->http://www.lydsy.com/JudgeOnline/problem.php?id=3637

我居然作死点了这道题

显然可以$lct$硬上,但是突然就不想写$lct$,没办法用树剖将就一下

Category: bzoj | Tags: 树状数组 线段树 LCT 树剖
2
29
2016
2

[坑]数据结构做傻了,于是再做点数据结构题

遍地都是坑,一个一个填,由于本人数据结构弱的一笔所以就慢慢填

由于日常%了Claris,于是得到了Claris的课件,题都是课件里找的_(:зゝ∠)_

你要课件?你tm真的以为我给你吗?

现在做了多少:  10/10

$3.7$  $qiancl:$喵的填坑填辣么慢

$3.10$  $qiancl:$嘿嘿嘿填完了

12
28
2015
2

[bzoj]4373: 算术天才⑨与等差数列

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4373

强制在线。。只能想到数据结构-。-

标算表示想不到-。-||| %Claris

我的做法是,用线段树维护区间最小值,区间哈希值,哈希采用平方和的方法(from 比利),对于一个知道了首项和公差的等差数列,其数列

$hash 值= n·a[1]·a[n]+ \frac{n(n-1)(2n-1)·k^2}{6}$

然后。。

Category: bzoj | Tags: hash gcd 线段树
12
18
2015
0

[bzoj]4345: [POI2016]Korale

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4345

 

首先考虑第一个问题

定义二元组$(x,y)$表示当前价值为$x$,位置在$y$,则$(x,y)$可以转移到$(x+a[y+1],y+1)$以及$(x-a[y]+a[y+1],y+1)$两个状态,这个先把$a$数组排序,再加个小根堆维护就行了,复杂度$\mathcal{O}\left(k\log k\right)$

Category: bzoj | Tags: 线段树 暴力
12
18
2015
0

[bzoj]3064: Tyvj 1518 CPU监控

-->http://www.lydsy.com/JudgeOnline/problem.php?id=3064

 

线段树裸题,维护六个标记,当前最大值,当前加标记,当前覆盖标记,历史最大值,历史最大加标记,历史最大覆盖标记。

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
#define oo -0x7f7f7f7f
#define nc() getchar()
inline int read(){
	int x=0,f=1;char ch=nc();for(;(ch<'0'||ch>'9')&&(ch!='-');ch=nc());
	if(ch=='-')ch=nc(),f=-1;for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x*f;
}inline void read(char&c){for(c=nc();c==' '||c=='\n';c=nc());}
#define N 100010
int i,j,k,m,n,x,y,a[N],L,R,V,q;bool F;
struct tree{int mx,cover,ad,pmx,pcover,pad;}T[N<<2];
#define lson k<<1,l,m
#define rson k<<1|1,m+1,r
#define max(a,b) ((a)>(b)?(a):(b))
inline void Mx(int&a,int b){if(b>a)a=b;}
#define up(k) (T[k].mx=max(T[k<<1].mx,T[k<<1|1].mx),Mx(T[k].pmx,max(T[k<<1].pmx,T[k<<1|1].pmx)))
void build(int k,int l,int r){
	T[k].cover=T[k].pcover=oo;
	if(l==r){T[k].mx=T[k].pmx=a[l];return;}
	int m=l+r>>1;build(lson),build(rson),T[k].pmx=oo,up(k);
}
#define Pcover(k,v) (Mx(T[k].pmx,v),Mx(T[k].pcover,v))
#define Pad(k,v) (Mx(T[k].pmx,T[k].mx+v),T[k].cover>oo?Mx(T[k].pcover,T[k].cover+v):Mx(T[k].pad,T[k].ad+v))
#define Cover(k,v) (Mx(T[k].pmx,T[k].mx=v),Mx(T[k].pcover,T[k].cover=v),T[k].ad=0)
#define Ad(k,v) (Mx(T[k].pmx,T[k].mx+=v),T[k].cover>oo?Mx(T[k].pcover,T[k].cover+=v):Mx(T[k].pad,T[k].ad+=v))
inline void down(int k){
	if(T[k].pad)Pad(k<<1,T[k].pad),Pad(k<<1|1,T[k].pad),T[k].pad=0;
	if(T[k].pcover>oo)Pcover(k<<1,T[k].pcover),Pcover(k<<1|1,T[k].pcover),T[k].pcover=oo;
	if(T[k].ad)Ad(k<<1,T[k].ad),Ad(k<<1|1,T[k].ad),T[k].ad=0;
	if(T[k].cover>oo)Cover(k<<1,T[k].cover),Cover(k<<1|1,T[k].cover),T[k].cover=oo;
}
int ask(int k,int l,int r){
	if(L<=l&&R>=r)return F?T[k].pmx:T[k].mx;down(k);
	int m=l+r>>1,ans=oo;
	if(L<=m)Mx(ans,ask(lson));
	if(R>m)Mx(ans,ask(rson));return up(k),ans;
}
void change(int k,int l,int r){
	if(L<=l&&R>=r){if(F)Cover(k,V);else Ad(k,V);return;}down(k);
	int m=l+r>>1;if(L<=m)change(lson);if(R>m)change(rson);up(k);
}
int main(){
	for(n=read(),i=1;i<=n;++i)a[i]=read();
	for(build(1,1,n),q=read();q--;){
		char f;read(f),L=read(),R=read();
		if(f=='Q')F=0,printf("%d\n",ask(1,1,n));
		else if(f=='A')F=1,printf("%d\n",ask(1,1,n));
		else if(f=='P')F=0,V=read(),change(1,1,n);
		else F=1,V=read(),change(1,1,n);
	}
}

 

Category: bzoj | Tags: 线段树
12
17
2015
2

[bzoj]4358: permu

--->http://www.lydsy.com/JudgeOnline/problem.php?id=4358

(为了这题我还写邮件叫管理员开大时限,indecision然而并没有什么卵用

总之这题的话$\mathcal{O}\left(n\sqrt{n}\log n\right)$的复杂度应该是很显然的,因为题目给的是一个排列所以就是一个求区间连续最长串的经典问题-。-,然后我算了一下复杂度-。-1.7亿,不,我要相信玄学---->然后我就写了0.0

Category: bzoj | Tags: 莫队 并查集 K-D tree 线段树

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com