离线处理 - Page 2

「BZOJ3339」Rmq Problem
DescriptionInputOutputSampleInput7502101321323143627SampleOutput30324HINT题解这一题在线似乎比较麻烦至于离线。。首先按照左端点将询问排序然后一般可以这样考虑首先如何得到1-i的sg值呢这个可以一开始扫一遍完成接着考虑l-r和l+1-r的答案有何不同显然是l-next[l]-1这一段所有sg值大于a[l]的变为a[l]这一步如果暴力修改的话只有30分但是修改区间我们可以想到线段树，这样就能a了[crayon-6740618a14868344853968/]&...
12014年5月17日8,524线段树,离线处理

「BZOJ2743」[HEOI2012] 采花
Description萧芸斓是Z国的公主，平时的一大爱好是采花。今天天气晴朗，阳光明媚，公主清晨便去了皇宫中新建的花园采花。花园足够大，容纳了n朵花，花有c种颜色（用整数1-c表示），且花是排成一排的，以便于公主采花。公主每次采花后会统计采到的花的颜色数，颜色数越多她会越高兴！同时，她有一癖好，她不允许最后自己采到的花中，某一颜色的花只有一朵。为此，公主每采一朵花，要么此前已采到此颜色的花，要么有相当正确的直觉告...
02014年5月14日5,680树状数组,离线处理
「BZOJ1878」[SDOI2009] HH的项链
DescriptionHH有一串由各种漂亮的贝壳组成的项链。HH相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。HH不断地收集新的贝壳，因此，他的项链变得越来越长。有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？这个问题很难回答。。。因为项链实在是太长了。于是，他只好求助睿智的你，来解决这个问题。Input第一行：一个整数N，表示项链的长度。第二行：...
52014年5月13日9,262树状数组,离线处理
「POJ2828」Buy Tickets
DescriptionRailwayticketsweredifficulttobuyaroundtheLunarNewYearinChina,sowemustgetupearlyandjoinalongqueue…TheLunarNewYearwasapproaching,butunluckilytheLittleCatstillhadschedulesgoinghereandthere.Now,hehadtotravelbytraintoMianyang,SichuanProvinceforthewintercampselectionofthenationalteamofOlympiadinInformatics.Itwasoneo’clocka.m.anddarkoutside.Chillwindfromthenorthwestdidnot...
02014年3月1日4,271线段树,离线处理
「BZOJ1015」[JSOI2008] 星球大战starwar
Description很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反...
32014年2月23日7,899并查集,离线处理
「CF295B」Greg and Graph
Greghasaweigheddirectedgraph,consistingof n vertices.Inthisgraphanypairofdistinctverticeshasanedgebetweentheminbothdirections.Greglovesplayingwiththegraphandnowhehasinventedanewgame:Thegameconsistsof n steps.Onthe i-thstepGregremovesvertexnumber xi fromthegraph.AsGregremovesavertex,healsoremovesalltheedgesthatgoinandoutofthisvertex.Beforeexecutingeachstep,Gregwantstoknowthesumofle...
02014年2月14日4,286floyd,离线处理