4
5
2014
0

【数学】我要学数学

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
0

树套树专题

树套树是我写到至今最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:
10
21
2013
0

【BZOJ2697】特技飞行【贪心】

开始以为是DP,但是仔细一想,动作k创造的价格只取决于它第一次出现的时间Sk和最后一次出现的时间Ek,则它创造的价值只可能为(Ek+Sk)*Ck。所以我们每次找最大价值的动作放在两侧直到放不下为止。

program p2697;
	var
		x:array[1..500] of longint;
		i,j,k,n,k1,max,where,tot:longint;
	begin
		readln(n,k);
		for i:=1 to k do
			read(x[i]);
		k1:=n+1; tot:=0;
		for i:=1 to k do begin
			k1:=k1-2;
			if k1<=0 then break;
			max:=-1;
			for j:=1 to k do
				if max<x[j] then begin
					max:=x[j]; where:=j;
				end;
			x[where]:=-1; tot:=tot+k1*max;
		end;
		writeln(tot);
	end.
Category: 贪心 | Tags:
10
21
2013
0

【BZOJ3280】小R的烦恼【费用流】

类似于那道BZOJ1221软件开发,把每天拆成两个,分别记为Xi,Yi,从S向Yi连一条流量Ai,费用为0的边。从Yi向Yi+1连一条流量maxint。对于每一个医院从Yi向Xi+Dk+1连一条流量为maxint,费用为Qk的边。从Xi向T连一条流量为k,费用为0的边。再对于每个大学都建一个节点Mi,从Mi向X1连一条流量为maxint,费用为Pi的边,从S向Mi连一条流量为Li,费用为0的边。这个网络的最小费用最大流的费用就是答案。开始数组开太大,估计是fillchar花了太多时间就T了。后来把数组改小就A了。

program p3280;
    const
        maxn=1000000000;
		modd=100000;
    type
        bian=record
            next,point,w,f:longint;
        end;
    var
		ii,t,tt,i,j,n,m,k,len,totpoint,totflow,totw,totnum:longint;
        a,l,pp,q,d:array[1..10000] of longint;
        b:array[0..200000] of bian;
        p,after,dis:array[0..10000] of longint;
        x:array[1..100000] of longint;
        pd:array[0..10000] of boolean;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    procedure ade(k1,k2,k3,k4:longint);
        begin
            inc(len);
            b[len].point:=k2;
            b[len].next:=p[k1];
            b[len].f:=k3;
            b[len].w:=k4;
            p[k1]:=len;
        end;
    procedure add(k1,k2,k3,k4:longint);
        begin
            ade(k1,k2,k3,k4);
            ade(k2,k1,0,-k4);
        end;
    function spfa:boolean;
        var
            head,i,j,now:longint;
        begin
            fillchar(x,sizeof(x),0);
            fillchar(pd,sizeof(pd),false);
            fillchar(dis,sizeof(dis),$3f);
            fillchar(after,sizeof(after),-1);
            x[1]:=0; head:=1; now:=0; pd[0]:=true; dis[0]:=0;
            while head<>now do begin
                now:=now mod modd+1;
                i:=p[x[now]];
                while i<>-1 do begin
                    j:=b[i].point;
                    if (b[i].f>0) and (b[i].w+dis[x[now]]<dis[j]) then begin
                        dis[j]:=b[i].w+dis[x[now]];
                        after[j]:=i;
                        if pd[j]=false then begin
                            pd[j]:=true;
                            head:=head mod modd+1;
                            x[head]:=j;
                        end;
                    end;
                    i:=b[i].next;
                end;
                pd[x[now]]:=false;
            end;
            if after[totpoint]>-1 then exit(true) else exit(false);
        end;
    function change:longint;
        var
            k,ans,tot,num,i,j:longint;
        begin
            i:=totpoint; j:=after[i]; k:=maxn;
            while j<>-1 do begin
                k:=min(k,b[j].f);
                i:=b[j xor 1].point;
                j:=after[i];
            end;
            ans:=0; i:=totpoint; j:=after[i];
            while j<>-1 do begin
                ans:=ans+k*b[j].w;
                dec(b[j].f,k);
                inc(b[j xor 1].f,k);
                i:=b[j xor 1].point;
                j:=after[i];
            end;
            totflow:=totflow+k;
            exit(ans);
        end;
    function dinic:longint;
        var
            ans:longint;
        begin
            ans:=0;
            while spfa do
                ans:=ans+change;
            exit(ans);
        end;
    begin
        readln(t);
        for tt:=1 to t do begin
            totnum:=0;
            readln(n,m,k);
            len:=-1;
            fillchar(p,sizeof(p),-1);
            fillchar(b,sizeof(b),0);
            for i:=1 to n do begin
                read(a[i]);
                totnum:=totnum+a[i];
            end;
            for i:=1 to m do
                read(l[i],pp[i]);
            for i:=1 to k do
                read(d[i],q[i]);
			for i:=m+1 to m+n-1 do
				add(i,i+1,maxn,0);
            for i:=1 to m do begin
                add(0,i,l[i],0);
				add(i,m+1,maxn,pp[i]);
            end;
            for i:=1 to n do begin
                add(0,i+n+m,a[i],0);
                for j:=1 to k do
                    if i+d[j]+1<=n then
						add(i+n+m,m+i+d[j]+1,maxn,q[j]);
            end;
            totpoint:=n+n+m+1;
            for i:=1 to n do
                add(m+i,totpoint,a[i],0);
            totflow:=0;
            totw:=dinic;
            if totflow<totnum then
                writeln('Case ',tt,': impossible')
            else
                writeln('Case ',tt,': ',totw);
        end;
    end.
Category: 费用流 | Tags:
10
21
2013
0

【BZOJ2190】【SDOI2008】仪仗队【欧拉函数】

线性筛一下欧拉函数,然后加起来×2加3即可。

program p2190;
	var
		x:array[1..400000] of boolean;
		prime,phi:array[1..400000] of longint;
		len,n,i,j,tot:longint;
	begin
		readln(n);
		dec(n);
		fillchar(x,sizeof(x),false);
		len:=0;
		for i:=2 to n do begin
			if x[i]=false then begin
				inc(len);
				phi[i]:=i-1;
				prime[len]:=i;
			end;
			j:=1;
			while (j<=len) and (prime[j]*i<=n) do begin
				x[i*prime[j]]:=true;
				if i mod prime[j]=0 then begin
					phi[prime[j]*i]:=phi[i]*prime[j]; break;
				end else
					phi[prime[j]*i]:=phi[i]*(prime[j]-1); 
				inc(j);
			end;
		end;
		tot:=0;
		for i:=1 to n do
			tot:=tot+phi[i];
		tot:=tot*2+3;
		writeln(tot);
	end.
Category: 欧拉函数 | Tags:

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