4
9
2014
0

【CodeChef月赛】2014.4

最后过了几题

7

本来放在这儿想提醒自己在最后把那道分数有小数的题目搞点分的,结果还是忘了QAQ。最后的rank是49,还行吧,rating居然到了3330+。

【T1】【patotes】直接枚举

【T2】【Shortest Path in Binary Trees】直接就和在树上求LCA一样log n算算就好了

【T3】【Chef and Digits】记录每个位置之前的0到9的数值和就可以了。

【T4】【Counting Matrices】预处理乘积小于等于n的数对个数,只要筛一下约数个数就可了。

【T5】【Divide the Tangerine】暴力即可

【T7】【Cards, bags and coins】把所有值全部都模m,然后再这个数组上DP。预处理逆元再在这个基础上预处理出在第i位取出若干个数使得其和模m位j的方案总数,这用逆元可以轻松解决,然后直接暴力DP就可以了。

【T8】【Final Battle of Chef】预处理每个点在第几次修改之后破产,这个直接整体二分做就可以了,对于每个修改向上跑16步就可以了。要注意的是这个东西不满足区间加减,所以要记录距离i位j的孩子到i时要丧失多少财产,这么做就可以了。总复杂度log3居然还能A。

Category: CodeChef | Tags:
4
9
2014
1

屯题计划

既然大爷们都在屯题刷日AC50题的副本,那我也来追随大爷们的脚步吧。

机房里的大爷们都去CTSC和APIO了。只有我一个傻×在这儿孤老终身屯水题QAQ。

膜拜XYZ大大进队,膜拜ZJ包揽国家队四个名额,小小的激动过后还是直面现实吧:我只是个傻X,还要屯水题QAQ

DZY大大和JC大大的副本居然都失败了,顿时有种不祥的预感QAQ

终于走到今天了,居然屯了一个月!今天晚上开始刷副本。

终于屯题结束了,日AC50题副本完成。截图留念:

现在屯了几题:

50

【BZOJ1529】【POI2005】Piggy Banks 并查集

【BZOJ1532】【POI2005】Dicing 网络流

【BZOJ1528】【POI2005】Toy Cars 贪心,每次删后继最远的点,用堆维护

【BZOJ1822】【JSOI2010】Frozen Nova 冷冻波 二分加网络流加恶心的计算几何,WA了很多次(最近真是刷不动题)

【BZOJ3520】dzy loves chemistry1 题解见专门的文章

【BZOJ1786】【Ahoi2008】Pair 配对 同1831

【BZOJ1826】【JSOI2010】缓存交换 1528+离散化

【BZOJ1531】【POI2005】Banks notes 优先队列来优化背包

【BZOJ3527】【ZJOI2014】力 FFT,现场AC真是不能更赞

【BZOJ2938】【POI2000】Viruses AC自动机,然后去掉所有可以匹配病毒的点判断有没有环即可

【BZOJ2946】【POI2000】Repetitions 和LCS2一模一样,那就贴代码了

【BZOJ2944】【POI2000】Code 卡特兰数预处理出来再递归就可以了。

【BZOJ2430】【POI2003】Chocolate  贪心

【BZOJ2610】【POI2003】Monkey 倒着处理,并查集维护

【BZOJ3545】【ONTAK2010】Peaks 启发式合并可以水过

【BZOJ3551】【ONTAK2010】Peaks加强版 jcvb告诉了我在线方法,然后我就把它加强放到了BZOJ上。用并查集维护然后转为子树第K大,然后就主席树做。

【BZOJ3524】【poi2014】Couriers 按位二分,挂个链表直接二分就可以了

【BZOJ3531】【SDOI2014】旅行 用线段树来维护树链剖分,改成动态开节点就可以了

【BZOJ3212】【Pku3468】A Simple Problem with integers 呵呵呵

【BZOJ1432】【ZJOI2009】Function 规律题,数据范围亮了,现场真的很难想到是O(1)题。

【BZOJ3529】【SDOI2014】数表 离线,线性筛,树状数组。貌似我常数写翔了QAQ

【BZOJ3522】【POI2014】Hotels DZY作死的题面又黑我。。做作业做的无聊死了那就回来屯题吧。直接枚举使得三个点在不同子树中的点然后DP即可。

【BZOJ3530】【SDOI2014】数数 裸的AC自动机+数位DP。第一次知道原来10^9+7不等于10e9+7...我个沙茶

【BZOJ2338】【HNOI2011】数矩形 不靠谱的乱搞方法,不知道是数据弱还是可以证明复杂度还是出题人就是要考这个,真是凌乱。

【BZOJ1875】【SDOI2009】HH去散步 矩乘

【BZOJ1861】【ZJOI2006】书架 屯题计划终于过半,感觉心情舒畅啊。裸平衡树,乱搞即可。

【BZOJ3091】城市旅行 LCT逗比题,莫名其妙的WA+莫名其妙的AC,真是不能多说

【BZOJ1821】【JSOI2010】部落划分 并查集水题

【BZOJ3555】【CTSC2014】企鹅QQ hash,福利题

【BZOJ3054】【CQOI2014】危桥 网络流搞搞

【BZOJ2423】【HAOI2010】最长公共子序列 DP,要用滚动数组

【BZOJ3438】小M的作物 裸最小割

【BZOJ3439】kpm的MC密码 所有倒序然后再Trie树上做子树第K大

【BZOJ1880】【SDOI2009】Elaxia的路线 最短路乱搞(最近完全无法刷题QAQ)

【BZOJ2565】最长双回文串 学了一下manache,拿这个练练手

【BZOJ3144】【HNOI2013】切糕 神最小割

【BZOJ3208】花神的秒题计划I 水题

【BZOJ3209】花神的数论题 数位DP

【BZOJ3211】花神游历各国 树状数组+并查集。0真是卡死我了

【BZOJ3038】上帝造题的七分钟2 同3211,终于上40了,希望就在前方

【BZOJ1978】【BeiJing2010】取数游戏 game 暴力DP,居然被卡常数了QAQ

【BZOJ1026】【SCOI2009】windy数 数位DP水题

【BZOJ1786】【AHOI2008】配对 双倍经验不解释

【BZOJ1758】【WC2010】重建计划 二分+点分治+单调队列,卡常数真是猥琐

【BZOJ3565】DZY loves Chinese 逗比题23333

【BZOJ2668】【CQOI2012】交换棋子 费用流,建图细节有点恶心,WA90了好久

【BZOJ2659】【Beijing wc2012】算不出的算式 找规律

【BZOJ2752】【HAOI2012】高速公路(road) 贴了城市旅行LCT的代码(慢的一比)。。这道题用线段树做就可以了。

【BZOJ3560】DZY Loves Math V 多元积函数,开始MLE,后来数组开小了QAQ(终于只剩下一题了)

【BZOJ3561】DZY Loves Math VI 直接上莫比乌斯函数乱搞 

Category: POI | Tags:
4
6
2014
0

这么弱搞什么OI

清明放假!有CF!上次WC的时候打CF进了div 1结果记录清零,这一次正好刷回去!刚转C++,那就用C++写吧。

恩A题很简单,尼玛怎么CE了。哦交成pascal了,再交,怎么又CE!仔细一看忘记inlcude cstring。然后A题就跪了。

恩B题很简单,加加减减就可以了,尼玛怎么WA了,改了两下过了,最后忘记long long,fst了。

恩C题很简单,不就是前面全部互质最后加一下,尼玛怎么WA了,哦忘记特判长度为1的情况了。

恩D题很简单一遍过了。

恩E题很简单,归并排序预处理一下就好了,尼玛死也调不出来,用不习惯C++怎么也写不对,最后就滚粗了。

尼玛我这么弱还搞什么OI,尼玛我这么弱还搞什么省选,直接切腹自尽算了。看着那么蓝名和1664的rating真是想一头撞死

五一的时候应该还能做一次CF,那一次如果再进不了div1我就转回pascal。

Category: 未分类 | Tags:
4
5
2014
1

【数学】我要学数学

ZJOI2014day1居然有两道数学题,再加上WC的经历,看来这个世界不会数学是混不成OI了,于是现在开始学数学吧。。。

膜拜了策神的博客,感触颇多,也学到了很多,做了几道题。

【BZOJ1101】【POI2007】ZAP 用莫比乌斯函数带进去搞搞就好了。

【BZOJ1693】jzptab 方法和上面差不多,莫比乌斯函数带进去然后再代换求和指标,把问题转化为求一个Dirichlet卷积。然后就线性筛做就可以了。

【BZOJ3309】方法同上,最后化出来一个感觉很靠谱的式子,但是要求f和µ的Dirichlet卷积,可以发现当为k个指数相同质数相乘时卷积为(-1)k+1,否则为0。的开始我只会O(nloglogn)的算法,显然TLE,后来一想只要先筛莫比乌斯函数,然后对于每个非0项自乘就可以了,非常简单而且复杂度O(n)

 

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
long long s[10000010],prime[10000000],pd[10000010],len,n,m;
void makeit()
{
	long long n=10000000;
	memset(s,0x00,sizeof s);
	memset(pd,0x00,sizeof pd);
	for (long long i=2;i<=n;i++)
	{
		if (!pd[i]) 
		{
			len++; prime[len]=i; s[i]=1;
		}
		for (long long j=1;j<=len;j++)
		{
			if (prime[j]*i>n) break;
			pd[prime[j]*i]=1;
			if (i%prime[j]==0)
			{
				s[i*prime[j]]=0; break;
			} else s[i*prime[j]]=-s[i];
		}
	}
	for (long long i=2;i<=int(sqrt(n));i++)
		if (s[i]!=0)
			for (long long j=i;j<=n;j=j*i)
				s[j]=s[i];
	for (long long i=2;i<=n;i++) s[i]+=s[i-1];
}
int main()
{
	int t; makeit();
	scanf("%d",&t);
	for (;t;t--)
	{
		scanf("%lld%lld",&n,&m);
		if (n>m) swap(n,m); long long tot=0,next; 
		for (long long i=1;i<=n;i=next+1)
		{
			next=min(n/(n/i),m/(m/i));
			tot+=(s[next]-s[i-1])*(m/i)*(n/i);
		}
		printf("%lld\n",tot);
	}
	return 0;
}

 

Category: 数学题 | Tags:
3
29
2014
0

ZJOI2014dzy1总结

貌似我这人一直被遗憾笼罩着~

在ZJOIdzy1前停了两个半礼拜的文化课,这段时间浪的非常开心2333,虽然完全放开了化学竞赛(现在目测已经跪了)。这段时间学了一点有用的东西比如后缀自动机、快速傅里叶变换、母函数等等,也算是有了一次实力的飞跃。同时也干了一些无聊的事情,比如硬着头皮浪费两天敲完LCT维护SAM的BZOJ2555,实现了最基础的动态仙人掌并且上了一节自娱自乐的课。

至于今天的三道题目,其实我自己发挥的还是可以的,但是T1出了一点小差错,这有点让人不能容忍。接下来讲讲今天的几道题吧~从一个傻×的视角

首先T1喜闻乐见又是我们可爱的ZL前辈的题,这一次他继续了去年丽洁体的风格,数据再一次出错。而且题目本生也SXBK,在做题时我先看了T1,然后觉得太烦跳过去看T2,尼玛T2是什么东西,这个怎么优化?然后看T3,计算几何?数据结构?然后开始看样例,尼玛三个点的直线拟合拟合了半个小时还拟合不对,果断放弃回头看T1。结果T1花了两个多小时敲了个理论60分的代码,在最后10分钟的时候发现了一个小BUG,来不及改了,唉这真是一个忧桑的故事。这道题对于pascal来说细节实在是太繁琐,我分类讨论了整整9KB,但是貌似用了C++的STL库就方便了许多,dzy大大就用set砍了80分,唉。

T2居然是fft!真是捡了个大便宜。开始看到数据范围还以为是分块乱搞,但发现这个式子并不具备传递性。然后就没去自己想。后来觉得很像fft,但是找不到卷积,只好乱展开乱搞,突然发现拆成两项TMD不就是个裸的fft吗。然后就喜闻乐见的捞了100分。我考前两天才会写fft,试机时候敲得就是fft我会乱说?也就是靠着这个人品爆发我才过了100分。据说有些大爷没有想到是fft(比如教我fft的dzy大大和实力无比强大的大吧主),但是有些大爷用各种神奇的方法A了这道题,比如杜教的泰勒展开,wys的分治乘法(居然被松爷AC了,我知道他不会写fft,还以为他这题会跪),唉真是被虐爆了。

至于T3真是。。。唉,样例都推不出来,暴力都没法写,先跪一下dzy的模拟退火。接下来复述一下全场rank3的金策大爷的原话:首先我们推出点到直线距离公式,然后设直线的方程,然后。。。策神停顿了一下,说:接下来我们用偏微分乱搞,然后一通乱解,就好了。我这种把学数学的时间都拿来看化学的人直接交出了我的膝盖。

至于排名。。Rank20左右吧。把noip的优势几乎浪没,估计还可以死皮赖脸的蹭在前16。但是既然没了noip的优势,就和很多大爷站在了同一起跑线上,但是以我现在的实力是几乎没有胜算的。距离第二次省选还有两个月,时间还算充足吧,是要再好好学习努力一番了。至于转语言,我言出必行!

 

Category: 未分类 | Tags:
2
14
2014
0

WC2014参赛感言

       意外地,今年我被选去参加WC2014。作为学军选手中实力比较薄弱的一名,我在出发前有过期待,也有点紧张,但是现在回顾我一周的WC之旅,我真是收获了很多很多。

       我和jcvb,fancycoder,lsmll三位大爷分在一个寝室(最后他们三位都是一等奖),虽然这让我压力山大,但是因此我一周的问题都有了去处,这也算是一种幸运吧。一周的寝室生活让我印象最深刻是一次codeforces的比赛,那天晚上熄灯后我们熬夜打比赛到凌晨两点,虽然有点疲惫,但也是格外的欢乐。

       WC中为我们上课的都是信息编程中的顶级高手,蒟蒻表示很多都听不懂。。。。。。不过尽管如此,我还是学到了很多,长了见识。乔明达的有限状态自动机,陈立杰的可持久化数据结构,还有其他以前根本没有见识过的例如具体数学、纳什均衡等方面的知识都让人神往。在课堂上,老师们耐心的为选手们解答各类的问题,现场也常常陷入激烈的争执和观点碰撞中(尽管如此,我有时还是根本听不懂)。。。当然了,winter camp

这一严肃的活动中,也有许多趣事。广开小号的yangff在一夜之间红遍了大江南北,IOI金牌选手许昊然说得好:“我们在座的都是yangff的小号,信不信我换一个马甲再和你说这句话。”这些事WC注入了欢笑与活力。

       当然,还有一个让人难以忘怀的小插曲就是汉字拼写大赛了。我和全场rank1的金策(Orz…)一组代表浙江队进入了复赛。(话说多亏他把平均分拉到了前十五。。不然连复赛都进不了)然后便有了浙江队让人苦笑不得的战绩。。。两次进入加赛,两次离决赛只有一步之遥,却又全部都抱憾下场。在我看来,这样的比赛让高二高三的学长和金策组队参加可能会更有优势。

       最后说一说最后的测试吧。虽然比赛时间有五个小时,但时间过的实在是太快太快了。这一次的两道常规题分别考了数学方面的内容和数据结构(Orz陈立杰的动态维护点分治)。由于我是数学渣,第一题想了一个多小时最后孩还只是打了个暴力。。。第二题在现场时我认为写出来了40分,而且和暴力对拍貌似也没什么大问题。而第三题我认为是三道题中最有新意的,虽然有反汇编这一bug,但是出题的思想的确很好。这一题我花了较多的时间最后拿了59分。在我走出试场时我的估分是109分,如果真是这样的我就一等奖了。唉。。可惜天有不测风云,我第二题没有看到取模。。QAQ。。结果白白丢了20分,在那道数据后我加上取模自己重新评测瞬间多了20分。。。可惜我无法回到考场去告诉自己第二题要取模,(话说这是我第二次栽在了取模上,在初三NOIP时我因为没看见取模差点没拿一等奖)于是乎我就抱着二等奖回到了杭州。而我的室友金策斩下了全场第一,为学校争得了荣誉,在未来的信奥学习生活中,我会继续努力,向金策学习,尽量避免低级失误。尽管我的水平不高,但是我的OI路还长,我坚信:

       ——OIer不回头,菜鸟变大牛。

Category: 未分类 | Tags:
1
9
2014
1

树套树专题

树套树是我写到至今最DT的数据库结构了吧。。。

【BZOJ3196】【Tyvj 1730】二逼平衡树

线段树套TREAP,nlog3n

program p3196;
    type
        tree=record
            l,r,w,f,size:longint;
        end;
    var
        t:array[0..4000000] of tree;
        x,root:array[0..500000] of longint;
        i,j,n,m,len,ans,l,r,mid,k1,k2,k3,k4,k5,k6:longint;
        ch:char;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    function max(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k2) else exit(k1);
        end;
    procedure zig(pf,f,k:longint);
        begin
            if t[pf].l=f then t[pf].l:=k else if t[pf].r=f then t[pf].r:=k;
            t[f].l:=t[k].r; t[k].r:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zag(pf,f,k:longint);
        begin
            if t[pf].l=f then t[pf].l:=k else if t[pf].r=f then t[pf].r:=k;
            t[f].r:=t[k].l; t[k].l:=f; t[f].size:=t[t[f].l].size+t[t[f].r].size+1;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure insert(f,k1,k2:longint);
        begin
            inc(t[k1].size);
            if t[k1].w>t[k2].w then begin
                if t[k1].l=0 then t[k1].l:=k2 else insert(k1,t[k1].l,k2);
                if t[k1].f<t[k2].f then zig(f,k1,k2);
            end else begin
                if t[k1].r=0 then t[k1].r:=k2 else insert(k1,t[k1].r,k2);
                if t[k1].f<t[k2].f then zag(f,k1,k2);
            end;
        end;
    procedure buildtree(k1,k2,k3:longint);
        var
            now,i,j:longint;
        begin
            root[k1]:=len+1; now:=len-k2+1; len:=len+k3-k2+1;
            for i:=k2 to k3 do begin
                t[i+now].w:=x[i]; t[i+now].size:=1; t[i+now].f:=random(1000000);
                if i<>k2 then begin
                    insert(0,root[k1],i+now); 
                    if (t[i+now].l=root[k1]) or (t[i+now].r=root[k1]) then root[k1]:=i+now; 
                end;
            end;
            if k2<>k3 then begin
                buildtree(k1*2,k2,(k2+k3) shr 1);
                buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
            end;
        end;
    function findallnum(k1,k2:longint):longint;
        begin
            if k1=0 then exit(0);
            if k2<t[k1].w then exit(findallnum(t[k1].l,k2));
            exit(findallnum(t[k1].r,k2)+1+t[t[k1].l].size);
        end;
    function pd(k1,k2,k3,k4,k5,k6:longint):longint;
        var
            k:longint;
        begin
            if (k2>k5) or (k3<k4) then exit(0);
            if (k2>=k4) and (k3<=k5) then exit(findallnum(root[k1],k6));
            exit(pd(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+pd(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
        end;
    function findwhere(k,k1,k2,f:longint):longint;
        var
            k3,k4:longint;
        begin
            if t[k1].w=k2 then begin
                while true do begin
                    if t[k1].l=0 then begin
                        if f=0 then root[k]:=t[k1].r else begin
                            if k1=t[f].l then t[f].l:=t[k1].r else t[f].r:=t[k1].r;
                        end;
                        t[k1].r:=0;
                        exit(k1);
                    end else if t[k1].r=0 then begin
                        if f=0 then root[k]:=t[k1].l else begin
                            if k1=t[f].l then t[f].l:=t[k1].l else t[f].r:=t[k1].l;
                        end;
                        t[k1].l:=0;
                        exit(k1);
                    end else begin
                        k3:=f;
                        if t[t[k1].l].f>t[t[k1].r].f then begin f:=t[k1].l; zig(k3,k1,t[k1].l); end else begin f:=t[k1].r; zag(k3,k1,t[k1].r); end;
                        if k3=0 then root[k]:=f;
                        dec(t[f].size);
                    end;
                end;
            end;
            dec(t[k1].size);
            if t[k1].w>k2 then exit(findwhere(k,t[k1].l,k2,k1)) else exit(findwhere(k,t[k1].r,k2,k1));
        end;
    procedure change(k1,k2,k3,k4,k6,k5:longint);
        var
            k:longint;
        begin
            if (k2>k4) or (k3<k4) then exit;
            if (k2=k3) then begin
                t[root[k1]].w:=k5; exit;
            end;
            k:=findwhere(k1,root[k1],k6,0); t[k].size:=1;
            t[k].w:=k5; insert(0,root[k1],k);  
            if (t[k].l=root[k1]) or (t[k].r=root[k1]) then root[k1]:=k;
            change(k1*2,k2,(k2+k3) shr 1,k4,k6,k5);
            change(k1*2+1,(k2+k3) shr 1+1,k3,k4,k6,k5);
        end;
    function findnum(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(0);
            if (k2>=k4) and (k3<=k5) then exit(findallnum(root[k1],k6));
            exit(findnum(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findnum(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
        end;
    function findlesss(k1,k2:longint):longint;
        begin
            if k1=0 then exit(-maxlongint);
            if k2<=t[k1].w then exit(findlesss(t[k1].l,k2));
            exit(max(findlesss(t[k1].r,k2),t[k1].w));
        end;
    function findmore(k1,k2:longint):longint;
        begin
            if k1=0 then exit(maxlongint);
            if k2>=t[k1].w then exit(findmore(t[k1].r,k2));
            exit(min(findmore(t[k1].l,k2),t[k1].w));
        end;
    function findmax(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(-maxlongint);
            if (k2>=k4) and (k3<=k5) then {begin
                writeln(k2,' ',k3,' ',k4,' ',k5,' ',k6,' ',findlesss(root[k1],k6));}
                exit(findlesss(root[k1],k6));
            {end;}
            exit(max(findmax(k1*2,k2,(k2+k3) shr 1,k4,k5,k6),findmax(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)));
        end;
    function findmin(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(maxlongint);
            if (k2>=k4) and (k3<=k5) then exit(findmore(root[k1],k6));
            exit(min(findmin(k1*2,k2,(k2+k3) shr 1,k4,k5,k6),findmin(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6)));
        end;
    begin
        readln(n,m);
        for i:=1 to n do read(x[i]); readln;
        len:=0; buildtree(1,1,n);
        for i:=1 to m do begin
            read(k6);
            if k6=2 then begin
                readln(k1,k2,k3); 
                l:=0; r:=1000000001;
                while l<r do begin
                    mid:=(l+r) shr 1; k4:=pd(1,1,n,k1,k2,mid);
                    if k4>=k3 then begin
                        ans:=mid; r:=mid;
                    end else l:=mid+1;
                end;
                writeln(ans);
            end else if k6=3 then begin
                readln(k1,k2);
                change(1,1,n,k1,x[k1],k2);
                x[k1]:=k2;
            end else if k6=1 then begin
                readln(k1,k2,k3);
                writeln(findnum(1,1,n,k1,k2,k3-1)+1);
            end else if k6=4 then begin
                readln(k1,k2,k3);
                writeln(findmax(1,1,n,k1,k2,k3));
            end else if k6=5 then begin
                readln(k1,k2,k3);
                writeln(findmin(1,1,n,k1,k2,k3));
            end;
        end;
    end.

【BZOJ2141】排队

用树套树来维护逆序对个数。挺巧妙的。nlog2n

program p2141;
    type
        tree=record
            father,l,r,w,size:longint;
        end;
    var
        t:array[0..2000000] of tree;
        w,root,x,y:array[0..3000000] of longint;
        i,j,n,m,len,k1,k2:longint;
        tot:int64;
    procedure zig(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; t[k].father:=t[f].father;
            if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
            t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
            t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zag(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; t[k].father:=t[f].father;
            if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
            t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
            t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure up(k,k1:longint);
        var
            f1,f2:longint;
        begin
            while (k<>k1) do begin
                f1:=t[k].father; f2:=t[f1].father;
                if f1=k1 then begin
                    if k=t[f1].l then zig(k) else zag(k);
                    exit;
                end;
                if k=t[f1].l then begin
                    if f1=t[f2].l then begin zig(f1); zig(k); end else begin zig(k); zag(k); end;
                end else if f1=t[f2].l then begin zag(k); zig(k); end else begin zag(f1); zag(k); end;
                if f2=k1 then exit;
                end;
        end;
    procedure insert(k1,k2:longint);
        begin
            inc(t[k1].size);
            if t[k2].w>t[k1].w then begin
                if t[k1].r=0 then begin t[k1].r:=k2; t[k2].father:=k1; end else insert(t[k1].r,k2);
            end else begin
                if t[k1].l=0 then begin t[k1].l:=k2; t[k2].father:=k1; end else insert(t[k1].l,k2);
            end;
        end;
    procedure buildtree(k1,k2,k3:longint);
        var
            now,i,j:longint;
        begin
            inc(len); root[k1]:=len; now:=len-k2; len:=len+k3-k2;
            for i:=k2 to k3 do begin
                t[now+i].w:=w[i]; t[now+i].size:=1;
                if i<>k2 then begin
                    insert(root[k1],now+i);
                    {if k1=1 then begin
                        writeln(root[k1]);
                        for j:=1 to n do
                            writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);
                        readln;
                    end;}
                    up(now+i,root[k1]); root[k1]:=now+i;
                end;
            end;
            if k2<>k3 then begin
                buildtree(k1*2,k2,(k2+k3) shr 1);
                buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
            end;
        end;
    procedure sort(first,en:longint);
        var
            i,j:longint;
        begin
            i:=first; j:=en; x[0]:=x[i];
            while i<j do begin
                while (i<j) and ((w[x[j]]>w[x[0]]) or ((w[x[j]]=w[x[0]]) and (x[j]>=x[0]))) do dec(j);
                if i<j then x[i]:=x[j];
                while (i<j) and ((w[x[i]]<w[x[0]]) or ((w[x[i]]=w[x[0]]) and (x[i]<x[0]))) do inc(i);
                if i<j then x[j]:=x[i];
            end;
            x[i]:=x[0];
            if i>first+1 then sort(first,i-1);
            if i<en-1 then sort(i+1,en);
        end;
    function lowbit(k:longint):longint;
        begin
            exit(k and (-k));
        end;
    procedure addin(k:longint);
        var
            i:longint;
        begin
            i:=k;
            while i<=n do begin
                x[i]:=x[i]+1;
                i:=i+lowbit(i);
            end;
        end;
    function addup(k:longint):longint;
        var
            i,j:longint;
        begin
            j:=0; i:=k;
            while i>0 do begin
                j:=j+x[i];
                i:=i-lowbit(i);
            end;
            exit(j);
        end;
    procedure swap(var k1,k2:longint);
        var
            i:longint;
        begin
            i:=k1; k1:=k2; k2:=i;
        end;
    function findallless(k1,k2:longint):longint;
        begin
            if k1=0 then exit(0);
            if t[k1].w>k2 then exit(findallless(t[k1].l,k2));
            exit(findallless(t[k1].r,k2)+t[t[k1].l].size+1);
        end;
    function findallmore(k1,k2:longint):longint;
        begin
            if k1=0 then exit(0);
            if t[k1].w<k2 then exit(findallmore(t[k1].r,k2));
            exit(findallmore(t[k1].l,k2)+t[t[k1].r].size+1);
        end;
    function findless(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(0);
            if (k2>=k4) and (k3<=k5) then exit(findallless(root[k1],k6));
            exit(findless(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findless(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
        end;
    function findmore(k1,k2,k3,k4,k5,k6:longint):longint;
        begin
            if (k2>k5) or (k3<k4) then exit(0);
            if (k2>=k4) and (k3<=k5) then exit(findallmore(root[k1],k6));
            exit(findmore(k1*2,k2,(k2+k3) shr 1,k4,k5,k6)+findmore(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5,k6));
        end;
    function findwhere(k1,k2:longint):longint;
        begin
            if t[k1].w=k2 then exit(k1);
            if t[k1].w<k2 then exit(findwhere(t[k1].r,k2));
            exit(findwhere(t[k1].l,k2));
        end;
    function findleft(k:longint):longint;
        begin
            while t[k].l<>0 do k:=t[k].l;
            exit(k);
        end;
    function findright(k:longint):longint;
        begin
            while t[k].r<>0 do k:=t[k].r;
            exit(k);
        end;
    procedure change(k1,k2,k3,k4,k5:longint);
        var
            k,i,j,k6,k7:longint;
        begin
            if (k2>k4) or (k3<k4) then exit;
            if (k2=k3) then begin
                t[root[k1]].w:=k5; exit;
            end;
            k:=findwhere(root[k1],w[k4]); up(k,root[k1]); root[k1]:=k;
            if t[k].l=0 then begin
                t[k].size:=1; t[t[k].r].father:=0; root[k1]:=t[k].r; t[k].r:=0;
            end else if t[k].r=0 then begin
                t[k].size:=1; t[t[k].l].father:=0; root[k1]:=t[k].l; t[k].l:=0;
            end else begin
                k6:=findright(t[k].l); k7:=findleft(t[k].r);
                up(k6,k); up(k7,t[k6].r); root[k1]:=k6; t[k7].l:=0;
                dec(t[k7].size); dec(t[k6].size); t[k].father:=0;
            end;
            t[k].w:=k5; insert(root[k1],k);
            change(k1*2,k2,(k2+k3) shr 1,k4,k5); change(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
        end;
    begin
        {assign(input,'data.in'); reset(input);
        assign(output,'dat1a.out'); rewrite(output);}
        readln(n);
        for i:=1 to n do read(w[i]);
        len:=0;
        fillchar(t,sizeof(t),0);
        fillchar(root,sizeof(root),0);
        buildtree(1,1,n);
        for i:=1 to n do x[i]:=i;
        sort(1,n);
        for i:=1 to n do y[x[i]]:=i;
        fillchar(x,sizeof(x),0);
        for i:=n downto 1 do begin
            tot:=tot+addup(y[i]-1);
            addin(y[i]);
        end;
        writeln(tot);
        readln(m);
        {while true do begin
            read(i); writeln(findmore(1,1,n,1,n,i)); writeln(findless(1,1,n,1,n,i)); end;}
        for i:=1 to m do begin
            {writeln(root[1]);}{
        for j:=1 to n do
                writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);}
            readln(k1,k2);
            if w[k1]=w[k2] then begin writeln(tot); continue; end;
            if k1>k2 then swap(k1,k2);
        {   writeln(findmore(1,1,n,1,n,w[k1]+1),' ',findless(1,1,n,1,n,w[k1]-1),' ',findless(1,1,n,1,n,w[k2]-1),' ',findmore(1,1,n,1,n,w[k2]+1));
        }   if k1+1<>k2 then tot:=tot+findmore(1,1,n,k1+1,k2-1,w[k1]+1)-findless(1,1,n,k1+1,k2-1,w[k1]-1)+findless(1,1,n,k1+1,k2-1,w[k2]-1)-findmore(1,1,n,k1+1,k2-1,w[k2]+1);
            if w[k1]<w[k2] then inc(tot) else dec(tot);
            change(1,1,n,k1,w[k2]); 
            {for j:=1 to n do
                writeln(t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].father,' ',t[j].w);}
            change(1,1,n,k2,w[k1]);
            swap(w[k1],w[k2]);
            writeln(tot);
        end;
    end.

【BZOJ2120】数颜色

用颜色种类个数的SPLAY来维护同种颜色的下一只画笔的位置。用树套树来求解。nlog2n。据说树状数组套主席树也可以做,但我太弱了不会。

 

program p2120;
	type
		tree=record
		l,r,father,w,size:longint;
	end;
	var
		root,first:array[0..800000] of longint;
		ro:array[0..2000000] of longint;
		t:array[0..4000000] of tree;
		w,x:array[0..20000] of longint;
		i,j,n,m,k1,k2,len:longint;
		ch:char;
	procedure zig(k:longint);
		var
			f:longint;
		begin
			f:=t[k].father; t[k].father:=t[f].father;
			if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
			t[f].father:=k; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f;
			t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
		end;
	procedure zag(k:longint);
		var
			f:longint;
		begin
			f:=t[k].father; t[k].father:=t[f].father;
			if f=t[t[f].father].l then t[t[f].father].l:=k else if f=t[t[f].father].r then t[t[f].father].r:=k;
			t[f].father:=k; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f;
			t[f].size:=t[t[f].l].size+t[t[f].r].size+1; t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
		end;
	procedure up(k1,k2:longint);
		var
			f1,f2:longint;
		begin
			while (k1<>k2) and (t[k1].father<>k2) do begin
				f1:=t[k1].father; f2:=t[f1].father;
				if f2=k2 then begin
					if k1=t[f1].l then zig(k1) else zag(k1);
					exit;
				end;
				if k1=t[f1].l then begin
					if f1=t[f2].l then begin zig(f1); zig(k1); end else begin zig(k1); zag(k1); end;
				end else if f1=t[f2].l then begin zag(k1); zig(k1); end else begin zag(f1); zag(k1); end;
			end;
		end;
	procedure insert(k1,k2:longint);
		begin
			if k1=0 then exit;
			inc(t[k1].size);
			if t[k1].w<t[k2].w then begin
				if t[k1].r=0 then begin t[k1].r:=k2; t[k2].father:=k1; end else insert(t[k1].r,k2);
			end else if t[k1].l=0 then begin t[k1].l:=k2; t[k2].father:=k1; end else insert(t[k1].l,k2);
		end;
	function min(k1,k2:longint):longint;
		begin
			if k1<k2 then exit(k1) else exit(k2);
		end;
	function findless(k1,k2:longint):longint;
		begin
			if k1=0 then exit(maxlongint);
			if t[k1].w<=k2 then exit(findless(t[k1].r,k2));
			exit(min(findless(t[k1].l,k2),t[k1].w));
		end;
	procedure buildtree(k1,k2,k3:longint);
		var
			i,j,now:longint;
		begin
			now:=len-k2; root[k1]:=len; len:=len+k3-k2+1; first[k1]:=now;
			for i:=k2 to k3 do begin
				t[now+i].w:=x[i]; t[now+i].size:=1;
				if i<>k2 then begin
					insert(root[k1],now+i); up(now+i,0); root[k1]:=now+i;
				end;
			end;
			if k2<>k3 then begin
				buildtree(k1*2,k2,(k2+k3) shr 1);
				buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
			end;
		end;
	procedure getchar(var ch:char);
		begin
			repeat
				read(ch);
			until(ch>='A') and (ch<='Z');
		end;
	function findbig(k1,k2:longint):longint;
		begin
			if k1=0 then exit(0);
			if t[k1].w>k2 then exit(findbig(t[k1].l,k2)+1+t[t[k1].r].size);
			exit(findbig(t[k1].r,k2));
		end;
	function findanswer(k1,k2,k3,k4,k5:longint):longint;
		begin
			if (k2>k5) or (k3<k4) then exit(0);
			if (k2>=k4) and (k3<=k5) then exit(findbig(root[k1],k5));
			exit(findanswer(k1*2,k2,(k2+k3) shr 1,k4,k5)+findanswer(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5));
		end;
	function findmorewhere(k1,k2:longint):longint;
		var
			k:longint;
		begin
			if k1=0 then exit(0);
			if t[k1].w>=t[k2].w then exit(findmorewhere(t[k1].l,k2));
			k:=findmorewhere(t[k1].r,k2);
			if k=0 then exit(k1) else exit(k);
		end;
	function findleft(k:longint):longint;
		begin
			while t[k].l<>0 do k:=t[k].l;
			exit(k);
		end;
	function findright(k:longint):longint;
		begin
			while t[k].r<>0 do k:=t[k].r;
			exit(k);
		end;
	procedure delete(k1,k2:longint);
		var
			l,r:longint;
		begin
			up(k2,0); root[k1]:=k2;
			if t[k2].l=0 then begin
				t[t[k2].r].father:=0; t[k2].size:=1; root[k1]:=t[k2].r;	t[k2].r:=0; 
			end else if t[k2].r=0 then begin
				t[t[k2].l].father:=0; t[k2].size:=1; root[k1]:=t[k2].l;	t[k2].l:=0;
			end else begin
				l:=findright(t[k2].l); r:=findleft(t[k2].r);
				up(l,0); up(r,l); root[k1]:=l;
				dec(t[l].size); dec(t[r].size); 
				t[r].l:=0; t[k2].father:=0;
			end;
		end;
	procedure changetreew(k1,k2,k3:longint);
		var
			k:longint;
		begin
			k:=first[k1]+k2;
			delete(k1,k); t[k].w:=k3;
			insert(root[k1],k); up(k,0); root[k1]:=k;
		end;
	procedure changew(k1,k2,k3,k4,k5:longint);
		begin
			if (k2>k4) or (k3<k4) then exit;
			changetreew(k1,k4,k5);
			if k2=k3 then exit;
			changew(k1*2,k2,(k2+k3) shr 1,k4,k5);
			changew(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
		end;
	procedure changex(k,color:longint);
		var
			l,r:longint;
		begin
			up(k,0); ro[w[k]]:=k;
			if t[k].l=0 then begin
				t[t[k].r].father:=0; t[k].size:=1; ro[w[k]]:=t[k].r; t[k].r:=0; 
			end else if t[k].r=0 then begin
				t[t[k].l].father:=0; t[k].size:=1; ro[w[k]]:=t[k].l;
				l:=findright(t[k].l); x[l]:=n+1;
				changew(1,1,n,l,n+1); t[k].l:=0;
			end else begin
				l:=findright(t[k].l); r:=findleft(t[k].r);
				up(l,0); up(r,l); ro[w[k]]:=l;
				dec(t[l].size); dec(t[r].size); 
				t[r].l:=0; t[k].father:=0;
				x[l]:=r; changew(1,1,n,l,r);
			end;
			insert(ro[color],k); up(k,0); ro[color]:=k;
			if t[k].l<>0 then begin
				l:=findright(t[k].l); changew(1,1,n,k,x[l]); changew(1,1,n,l,k); x[k]:=x[l]; x[l]:=k;
			end else if t[k].r<>0 then begin
				r:=findleft(t[k].r); changew(1,1,n,k,r); x[k]:=r;
			end else begin
				x[k]:=n+1; changew(1,1,n,k,n+1);
			end;
		end;
	begin
		readln(n,m);
		fillchar(root,sizeof(root),0);
		fillchar(ro,sizeof(ro),0);
		fillchar(t,sizeof(t),0);
		for i:=1 to n do begin
			read(w[i]);
			t[i].w:=i; t[i].size:=1;
			insert(ro[w[i]],i); up(i,0); ro[w[i]]:=i; 
		end;
		for i:=1 to n do begin
			up(i,0);
			if t[i].r=0 then x[i]:=n+1 else x[i]:=findleft(t[i].r);
		end;
		len:=n+1;
		buildtree(1,1,n);
		for i:=1 to m do begin
			{for j:=1 to n do writeln(x[j],' ',w[j]);
			for j:=1 to 6 do writeln(ro[j]); 
			for j:=1 to n do writeln(j,' ',t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].w,' ',ro[w[j]]);
			writeln;
			for j:=1 to n*2 do writeln(first[j],' ',root[j]);
			for j:=1+n to n*2 do writeln(j,' ',t[j].l,' ',t[j].r,' ',t[j].size,' ',t[j].w);
			}getchar(ch);
			if ch='Q' then begin
				readln(k1,k2);
				writeln(findanswer(1,1,n,k1,k2));
			end else begin
				readln(k1,k2);
				if w[k1]=k2 then continue;
				changex(k1,k2); w[k1]:=k2;
			end;
		end;
	end.
Category: 数据结构 | Tags:
1
9
2014
0

LCT专题

 LCT,传说中的动态树,写得我蛋疼啊。

【BZOJ2002】【hnoi2012】弹飞绵羊

裸LCT,只需要维护深度。

program p2002;
    type
        tree=record
            l,r,father,size:longint;
        end;
    var
        t:array[0..200100] of tree;
        root:array[0..200100] of boolean;
        z,i,j,n,m,k1,k2,k3:longint;
    procedure change(k:longint);
        begin
            t[t[k].l].father:=k; t[t[k].r].father:=k;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zig(i:longint); 
        begin
            z:=t[i].r;t[i].r:=t[z].l;t[t[i].r].father:=i;t[z].l:=i;
            if i=t[t[i].father].l then t[t[i].father].l:=z else
            if i=t[t[i].father].r then t[t[i].father].r:=z;
            t[z].father:=t[i].father;t[i].father:=z;
            root[z]:=root[i] xor root[z];
            root[i]:=root[i] xor root[z];
            t[i].size:=t[t[i].l].size+t[t[i].r].size+1;
            t[z].size:=t[t[z].l].size+t[t[z].r].size+1;
       end;
    procedure zag(i:longint); 
       begin
            z:=t[i].l;t[i].l:=t[z].r;t[t[i].l].father:=i;t[z].r:=i;
            if i=t[t[i].father].l then t[t[i].father].l:=z else
            if i=t[t[i].father].r then t[t[i].father].r:=z;
            t[z].father:=t[i].father;t[i].father:=z;
            root[z]:=root[i] xor root[z];
            root[i]:=root[i] xor root[z];
            t[i].size:=t[t[i].l].size+t[t[i].r].size+1;
            t[z].size:=t[t[z].l].size+t[t[z].r].size+1;
       end;
    procedure up(k1:longint);
        var
            i,j:longint;
        begin
          while root[k1]=false do
                if t[t[k1].father].l=k1 then zag(t[k1].father) else zig(t[k1].father);
        end;
    procedure all_change(k:longint);
        var
            f:longint;
        begin
            up(k);
            while t[k].father<>0 do begin
                f:=t[k].father;
                up(f);
                root[t[f].r]:=true; root[k]:=false;
                t[f].r:=k; t[f].size:=t[t[f].r].size+t[t[f].l].size+1;
                up(k);
            end;
        end;
    begin
        fillchar(root,sizeof(root),true);
        readln(n);
        fillchar(t,sizeof(t),0);
        for i:=1 to n do begin
            read(t[i].father); t[i].size:=1; t[i].father:=t[i].father+i; if t[i].father>n then t[i].father:=n+1;
        end;
        t[n+1].size:=1;
        readln(m);
        for i:=1 to m do begin
            read(k1,k2); inc(k2);
            if k1=1 then begin
                all_change(k2); writeln(t[t[k2].l].size);
            end else begin
                read(k3);
                up(k2); t[t[k2].l].father:=t[k2].father;
                root[t[k2].l]:=true; t[k2].l:=0;
                t[k2].father:=k2+k3; if t[k2].father>n then t[k2].father:=n+1;
                t[k2].size:=t[t[k2].r].size+1;
            end;
        end;

【BZOJ2049】【Sdoi2008】Cave 洞穴勘测

LCT,只需要维护联通。

program p2049;
    type
        tree=record
            l,r,father:longint;
        end;
    var
        t:array[0..500000] of tree;
        rev:array[0..500000] of boolean;
        i,j,n,k1,k2,k3,k4,m:longint;
        ch:char;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure swap(var k1,k2:longint);
        var
            k:longint;
        begin
            k:=k1; k1:=k2; k2:=k;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            swap(t[k].l,t[k].r); rev[k]:=rev[k] xor true;
        end;
    procedure pushdown(k:longint);
        begin
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
        end;
    procedure zig(k:longint);
        var
            f:longint;
            bo:boolean;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
        end;
    procedure zag(k:longint);
        var
            f:longint;
            bo:boolean;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
        end;
    procedure splay(k:longint);
        begin
            pushdown(k);
            while splay_root(k)=true do
                if k=t[t[k].father].l then zig(k) else zag(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k);
                t[k].r:=now;
                now:=k;
                k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        var
            f:longint;
        begin
            f:=access(k);
            fz(f); splay(k);
        end;
    procedure link(k1,k2:longint);  
        var
            k:longint;
        begin
            makeroot(k1); t[k1].father:=k2; k:=access(k1); 
        end;
    procedure cut(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0;
        end;
    function findleft(k:longint):longint;
        begin
            pushdown(k);
            if t[k].l=0 then exit(k) else exit(findleft(t[k].l));
        end;
    begin
        readln(n,m);
        fillchar(rev,sizeof(rev),false);
        fillchar(t,sizeof(t),0);
        for i:=1 to m do begin
            read(ch);
            {for j:=1 to n do if rev[j]=true then writeln(true);}
            if ch='C' then begin
                for j:=1 to 6 do read(ch); readln(k1,k2);
                link(k1,k2);
            end else if ch='D' then begin
                for j:=1 to 6 do read(ch); readln(k1,k2);
                cut(k1,k2);
            end else begin
                for j:=1 to 4 do read(ch); readln(k1,k2);
                k3:=findleft(access(k1)); k4:=findleft(access(k2));
                if k3=k4 then writeln('Yes') else writeln('No');
            end;
        end;
    end.

【BZOJ2243】【SDOI2011】染色

LCT,需要一个区间覆盖的标记。

 

program p2243;
    type
        tree=record
            l,r,left,right,w,ans,father:longint;
        end;
    var
        t:array[0..110000] of tree;
        rev:array[0..110000] of boolean;
        color:array[0..110000] of longint;
        n,m,i,j,k1,k2,k3:longint;
        ch:char;
    procedure changecolor(k1,k2:longint);
        begin
            if k1=0 then exit;
            color[k1]:=k2; t[k1].w:=k2; t[k1].left:=k2; t[k1].right:=k2; t[k1].ans:=1;
        end;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure swap(var k1,k2:longint);
        var
            k:longint;
        begin
            k:=k1; k1:=k2; k2:=k;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            swap(t[k].l,t[k].r); swap(t[k].left,t[k].right); rev[k]:=rev[k] xor true; 
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
            if color[k]<>-1 then begin
                changecolor(t[k].l,color[k]); changecolor(t[k].r,color[k]); color[k]:=-1;
            end;
        end;
    procedure change(k:longint);
        begin
            pushdown(t[k].l); pushdown(t[k].r);
            t[k].left:=t[t[k].l].left; t[k].right:=t[t[k].r].right;
            if t[k].left=-1 then t[k].left:=t[k].w;
            if t[k].right=-1 then t[k].right:=t[k].w;
            t[k].ans:=t[t[k].l].ans+t[t[k].r].ans+1;
            if t[k].w=t[t[k].l].right then dec(t[k].ans);
            if t[k].w=t[t[k].r].left then dec(t[k].ans);
        end;
    procedure zig(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k); 
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
            change(f); {change(k);}
        end;
    procedure zag(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k); 
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
            change(f); {change(k);}
        end;
    procedure splay(k:longint);
        begin
            pushdown(k);
            while splay_root(k)=true do
                if k=t[t[k].father].l then zig(k) else zag(k);
            change(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k); t[k].r:=now; change(k); now:=k; k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        var
            f:longint;
        begin
            f:=access(k); fz(f); splay(k);
        end;
    procedure link(k1,k2:longint);
        var
            f:longint;
        begin
            makeroot(k1); t[k1].father:=k2; f:=access(k1);
        end;
    procedure cut(k1,k2:longint);
        var
            f:longint;
        begin
            makeroot(k1); access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0; change(k2);
        end;
    function findanswer(k1,k2:longint):longint;
        var
            f:longint;
        begin
            makeroot(k1); exit(t[access(k2)].ans);
        end;
    procedure rebuild(k1,k2,k3:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); changecolor(k,k3);
        end;
    begin
        readln(n,m);
        fillchar(t,sizeof(t),0);
        fillchar(rev,sizeof(rev),false);
        fillchar(color,sizeof(color),-1);
        for i:=1 to n do begin
            read(t[i].w); t[i].left:=t[i].w; t[i].right:=t[i].w;
        end; readln;
        t[0].w:=-1; t[0].left:=-1; t[0].right:=-1;
        for i:=1 to n-1 do begin
            readln(k1,k2); link(k1,k2);
        end;
        for i:=1 to m do begin
            read(ch);
            if ch='Q' then begin
                readln(k1,k2); writeln(findanswer(k1,k2));
            end else begin
                readln(k1,k2,k3); rebuild(k1,k2,k3);
            end;
        end;
    end.

【BZOJ2631】tree(伍一鸣)

双标记的LCT,PASCAL由于常熟原因T了一点。

program p2631;
    const
        modd=51061;
    type
        tree=record
            father,l,r,size:longint;
            w,ans:int64;
        end;
    var
        t:array[0..210000] of tree;
        x,y:array[0..210000] of int64;
        rev:array[0..210000] of boolean;
        i,j,n,m,k1,k2,k3:longint;
        ch:char;
    procedure chen(k1,k2:longint);
        begin
            if k1=0 then exit;
            x[k1]:=x[k1]*k2 mod modd; y[k1]:=y[k1]*k2 mod modd;
            t[k1].w:=t[k1].w*k2 mod modd; t[k1].ans:=t[k1].ans*k2 mod modd;
        end;
    procedure jia(k1,k2:longint);
        begin
            if k1=0 then exit;
         {   if y[k1]<>1 then begin
                chen(t[k1].l,y[k1]); chen(t[k1].r,y[k1]); y[k1]:=1;
            end;}
            x[k1]:=x[k1]+k2; t[k1].w:=t[k1].w+k2;  t[k1].ans:=t[k1].ans+k2*t[k1].size;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            t[k].l:=t[k].l xor t[k].r;
            t[k].r:=t[k].r xor t[k].l;
            t[k].l:=t[k].l xor t[k].r;
            rev[k]:=rev[k] xor true;
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
            if y[k]<>1 then begin
                chen(t[k].l,y[k]); chen(t[k].r,y[k]); y[k]:=1;
            end;
            if x[k]<>0 then begin
                jia(t[k].l,x[k]); jia(t[k].r,x[k]); x[k]:=0;
            end;
        end;
    procedure change(k:longint);
        begin
            if k=0 then exit;
            t[k].ans:=(t[t[k].l].ans+t[t[k].r].ans+t[k].w) mod modd;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zig(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
            change(f); 
        end;
    procedure zag(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
            change(f); 
        end;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure splay(k:longint);
        var
            f1,f2:longint;
        begin
            pushdown(k);
            while (splay_root(k)=true) do begin
                f1:=t[k].father; f2:=t[f1].father;
                if splay_root(f1)=false then begin
                    if k=t[t[k].father].l then zig(k) else zag(k);
                    break;
                end;
                pushdown(f2);
                if k=t[f1].l then begin
                    if f1=t[f2].l then begin zig(f1); zig(k); end else begin zig(k); zag(k); end;
                end else if f1=t[f2].l then begin zag(k); zig(k); end else begin zag(f1); zag(k); end;
            end;
            change(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k); t[k].r:=now; change(k); now:=k; k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        begin
            fz(access(k)); splay(k);
        end;
    procedure link(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); t[k1].father:=k2; k:=access(k1);
        end;
    procedure cut(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0; change(k2);
        end;
    procedure add1(k1,k2,k3:longint);
        begin
            makeroot(k1); jia(access(k2),k3);
        end;
    procedure add2(k1,k2,k3:longint);
        begin
            makeroot(k1); chen(access(k2),k3);
        end;
    function findanswer(k1,k2:longint):longint;
        begin
            makeroot(k1); exit(t[access(k2)].ans);
        end;
    begin
        readln(n,m);
        fillchar(t,sizeof(t),0);
        fillchar(x,sizeof(x),0);
        fillchar(rev,sizeof(rev),false);
        for i:=1 to n do begin
            y[i]:=1; t[i].size:=1; t[i].w:=1; t[i].ans:=1;
        end;
        for i:=1 to n-1 do begin
            readln(k1,k2);
            link(k1,k2);
        end;
        for i:=1 to m do begin
            read(ch);
            if ch='+' then begin
                readln(k1,k2,k3);
                add1(k1,k2,k3);
            end else if ch='/' then begin
                readln(k1,k2);
                writeln(findanswer(k1,k2));
            end else if ch='-' then begin
                read(k1,k2); cut(k1,k2);
                readln(k1,k2); link(k1,k2);
            end else begin
                readln(k1,k2,k3);
                add2(k1,k2,k3);
            end;
        end;
    end.

Category: 数据结构 | Tags:
1
9
2014
0

平衡树专题

 

好久没来这儿了,忙了好久的数据库结构,现在来除个草吧。

【BZOJ3223】【TYVJ1729】文艺平衡树

只需要一个翻转标记。华丽的nlogn复杂度。

program p3223;
    type
        tree=record
            rev:boolean;
            l,r,w,size,father:longint;
        end;
    var
        t:array[0..110000] of tree;
        i,j,n,len,k1,k2,m,k3:longint;
    procedure change(k:longint);
        begin
            if k=0 then exit;
            t[t[k].l].father:=k; t[t[k].r].father:=k;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure reversal(k:longint);
        var
            i:longint;
        begin
            if k=0 then exit;
            i:=t[k].l; t[k].l:=t[k].r; t[k].r:=i;
            t[k].rev:=not t[k].rev;
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if t[k].rev then begin 
                reversal(t[k].l); reversal(t[k].r); t[k].rev:=false;
            end;
        end;
    procedure zig(k:longint);
        var
            i:tree;
            f:longint;
        begin
            f:=t[k].father;
            pushdown(f); pushdown(k);
            i:=t[f]; t[f]:=t[k]; t[k]:=i;
            t[k].l:=t[f].r; t[f].r:=k; t[f].father:=t[k].father; t[k].father:=f;
            change(k); change(f);
        end;
    procedure zag(k:longint);
        var
            i:tree;
            f:longint;
        begin
            f:=t[k].father;
            pushdown(f); pushdown(k);
            i:=t[f]; t[f]:=t[k]; t[k]:=i;
            t[k].r:=t[f].l; t[f].l:=k; t[f].father:=t[k].father; t[k].father:=f;
            change(k); change(f);
        end;
    procedure build(now,l,r:longint);
        var
            mid:longint;
        begin
            t[now].rev:=false; 
            mid:=(l+r) shr 1;  t[now].w:=mid;
            if mid>l then begin
                t[now].l:=len+1; inc(len); build(len,l,mid-1);
            end;
            if mid<r then begin
                t[now].r:=len+1; inc(len); build(len,mid+1,r);
            end;
            change(now);
        end;
    function find(now,k:longint):longint;
        var
            l,r:longint;
        begin
            pushdown(now);
            l:=t[now].l; r:=t[now].r;
            if t[l].size=k-1 then exit(now);
            if t[l].size<k-1 then exit(find(r,k-t[l].size-1));
            exit(find(l,k));
        end;
    procedure up(k1,k2:longint);
        var
            i,j:longint;
        begin
            if k1=k2 then exit;
            if t[k1].father=k2 then begin
                if t[k2].l=k1 then zig(k1) else zag(k1);
                exit;
            end;
            i:=t[k1].father; j:=t[i].father;
            if k1=t[i].l then begin
                if i=t[j].l then begin zig(i); zig(k1); end else begin zig(k1); zag(i); end;
            end else
                if i=t[j].l then begin zag(k1); zig(i); end else begin zag(i); zag(k1); end;
            up(j,k2);
        end;
    begin
        readln(n,m);
        len:=1;
        t[0].size:=0;
        build(1,0,n+1);
        for i:=1 to m do begin
            readln(k1,k2);
            k3:=find(1,k1);
            up(k3,1);
            t[0].size:=0;
            k3:=find(1,k2+2);
            up(k3,t[1].r);
            t[0].size:=0;
            reversal(t[t[1].r].l);
        end;
        for i:=1 to n do begin
            k3:=find(1,i+1);
            write(t[k3].w);
            if i<>n then write(' ');
        end; 
    end.

Category: 数据结构 | Tags:
10
21
2013
0

【BZOJ1012】【JSOI2008】最大数maxnumber【倍增】

显然,如果使用倍增,用num[i,j]表示从i-2^j+1到i的所有数的最大值,则后面插入的数对前面插入的数是没有影响的。这样就可以使用倍增,插入和查找都是logn的复杂度,妥妥的。

program p1012;
	var
		num:array[1..200000,0..17] of int64;
		i,j:longint;
		m,d,k1,len,k2,now:int64;
		ch:char;
	function max(k1,k2:longint):longint;
		begin	
			if k1<k2 then exit(k2) else exit(k1);
		end;
	begin
		readln(m,d); k1:=0;
		fillchar(num,sizeof(num),$3f);
		for i:=1 to m do begin
			read(ch);
			if ch='A' then begin
				inc(len);
				readln(k2);
				k2:=(k2+k1) mod d;
				num[len,0]:=k2;
				for j:=1 to 17 do
					if 1 shl j<=len then
						num[len,j]:=max(num[len-1 shl (j-1),j-1],num[len,j-1])
					else break;
			end else begin
				readln(k2); k1:=0; now:=len;
				for j:=17 downto 0 do
					if k2 and (1 shl j)>0 then begin
						k1:=max(k1,num[now,j]);
						now:=now-(1 shl j);
					end;
				writeln(k1);
			end;
		end;
	end.
Category: 倍增 | Tags:

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