/2016/11/ 个人博客，（曾经）基本只放题解，现在随便写点啥了吧（ /archives/87/ 2016-11-29T23:24:00+08:00 ###Description 外面有一圈N个结点，中心有一个结点与N个结点都相连，总共就是2*N条边，删除N条边，使N+1个点连通，旋转相同视为等价，问有多少种情况。 ![1.jpg][1] ###Input 输入N，M 3 /archives/83/ 2016-11-27T12:35:00+08:00 ###Description 给一个长为n的序列a，每个数在0到v - 1之间，有m次操作。 操作1：每次询问一个区间中是否可以选出两个下标的集合X，Y，满足： 1.X和Y没有交集 2.设集合X中有一个元素是i，则其对集合X的贡献是a[i] + 1，要求集合X的元素的总贡献和集合Y的元素的总贡献 相等如果可以选出这两个集合，输出 Yuno否则输出 Yuki 操作2：修改一个区间l,r之间的数，使得所有l /archives/80/ 2016-11-17T00:28:00+08:00 ###Description 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作： 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x，且最大的数) 5.查询k在区间内的后继(后继定义为大于x，且最小的数) ###Input 第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数，表示有序序列 下面有m行，opt表示操作标号 若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名 若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数 若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱 若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继 ###Output 对于操作1,2,4,5各输出一行，表示查询结果 ###Sample Input 9 6 4 2 2 1 9 4 0 1 1 2 1 4 3 3 4 10 2 1 4 3 1 2 5 9 4 3 9 5 5 2 8 5 ###Sample Output 2 4 3 4 9 ###HINT 1.n和m的数据范围：n,mb?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) struct node { node *lc,*rc; int cnt; node(); }_null,*null=&_null; node::node(){lc=rc=null;cnt=0;} int pf; void erase(node *x) { if(x->lc!=null)erase(x->lc); if(x->rc!=null)erase(x->rc); delete x; } void modify(node *&x,int l,int r,int p,int v) { if(x==null)x=new node; x->cnt+=v; if(!x->cnt) { erase(x); x=null; return; } if(l!=r) { int f=(l+r)/2; if(plc,l,f,p,v); else modify(x->rc,f+1,r,p,v); } } struct group { node *x[50]; int mul[50],sz; inline int cnt() { int ret=0; for(int i=0;icnt*mul[i]; return ret; } inline group* lc(group *f) { f->sz=sz; for(int i=0;ix[i]=x[i]->lc,f->mul[i]=mul[i]; return f; } inline group* rc(group *f) { f->sz=sz; for(int i=0;ix[i]=x[i]->rc,f->mul[i]=mul[i]; return f; } }; int cnt(group *x,int l,int r,int ql,int qr) { if(l==ql&&r==qr)return x->cnt(); int t=(l+r)/2,ans=0; group ch; if(qllc(&ch),l,t,ql,min(t,qr)); if(qr>t)ans+=cnt(x->rc(&ch),t+1,r,max(ql,t+1),qr); return ans; } int kth(group *x,int l,int r,int rk) { if(l==r)return l; group ch; x->lc(&ch); int lcnt; if((lcnt=ch.cnt())>=rk) return kth(&ch,l,(l+r)/2,rk); else return kth(x->rc(&ch),(l+r)/2+1,r,rk-lcnt); } int gmax(group *x,int l,int r,int p) { if(!x->cnt())return 0; if(l==r)return l; int t=(l+r)/2; group ch; if(plc(&ch),l,t,p); if(r==p) { x->rc(&ch); if(ch.cnt())return gmax(&ch,t+1,r,p); return gmax(x->lc(&ch),l,t,t); } return max(gmax(x->lc(&ch),l,t,t),gmax(x->rc(&ch),t+1,r,p)); } int gmin(group *x,int l,int r,int p) { if(!x->cnt())return 0x7fffffff; if(l==r)return l; int t=(l+r)/2; group ch; if(p>t)return gmin(x->rc(&ch),t+1,r,p); if(l==p) { x->lc(&ch); if(ch.cnt())return gmin(&ch,l,t,p); return gmin(x->rc(&ch),t+1,r,t+1); } return min(gmin(x->lc(&ch),l,t,p),gmin(x->rc(&ch),t+1,r,t+1)); } #define nl 0 #define nr 100000001 node *root[50001]; int v[50001]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i /archives/76/ 2016-11-15T15:39:00+08:00 ###Description 教主最近学会了一种神奇的魔法，能够使人长高。于是他准备演示给XMYZ信息组每个英雄看。于是N个英雄们又一次聚集在了一起，这次他们排成了一列，被编号为1、2、……、N。 每个人的身高一开始都是不超过1000的正整数。教主的魔法每次可以把闭区间[L, R]（1≤L≤R≤N）内的英雄的身高全部加上一个整数W。（虽然L=R时并不符合区间的书写规范，但我们可以认为是单独增加第L（R）个英雄的身高） CYZ、光哥和ZJQ等人不信教主的邪，于是他们有时候会问WD闭区间 [L, R] 内有多少英雄身高大于等于C，以验证教主的魔法是否真的有效。 WD巨懒，于是他把这个回答的任务交给了你。 ###Input 第1行为两个整数N、Q。Q为问题数与教主的施法数总和。 第2行有N个正整数，第i个数代表第i个英雄的身高。 第3到第Q+2行每行有一个操作： （1）若第一个字母为“M”，则紧接着有三个数字L、R、W。表示对闭区间 [L, R] 内所有英雄的身高加上W。 （2）若第一个字母为“A”，则紧接着有三个数字L、R、C。询问闭区间 [L, R] 内有多少英雄的身高大于等于C。 ###Output 对每个“A”询问输出一行，仅含一个整数，表示闭区间 [L, R] 内身高大于等于C的英雄数。 ###Sample Input 5 3 1 2 3 4 5 A 1 5 4 M 3 5 1 A 1 5 4 ###Sample Output 2 3 ###HINT 【输入输出样例说明】 原先5个英雄身高为1、2、3、4、5，此时[1, 5]间有2个英雄的身高大于等于4。教主施法后变为1、2、4、5、6，此时[1, 5]间有3个英雄的身高大于等于4。 【数据范围】 对30%的数据，N≤1000，Q≤1000。 对100%的数据，N≤1000000，Q≤3000，1≤W≤1000，1≤C≤1,000,000,000。 ###Solution 分块可以做，然而花式分块更快。。 在每个操作的端点处划分，共分为最多4Q块，那么每个操作必会在一段连续块上 处理每块时，遍历所有包含它的操作，若为修改，则delta+=w，若为查询，则记录c-delta，然后将询问按c-delta排序 之后遍历该块中的数，二分+差分维护贡献 时间复杂度$$O(Q^2logQ+NlogQ)$$ ##Code ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) int n,m,h[1000001],q[3000][4],bl[12010],ans[3000],tmp[3000]; struct yjq { int x,id; inline bool operator 1; else l=(l+r)>>1; } tmp[l]++; } for(int j=fm-1,t=0;j>=0;j--) { t+=tmp[j]; ans[f[j].id]+=t; } } for(int i=0;i /archives/74/ 2016-11-15T08:21:00+08:00 ###Description “寄没有地址的信，这样的情绪有种距离，你放着谁的歌曲，是怎样的心心静，能不能说给我听。” 失忆的Eden总想努力地回忆起过去，然而总是只能清晰地记得那种思念的感觉，却不能回忆起她的音容笑貌。 记忆中，她总是喜欢给Eden出谜题：在 valentine’s day 的夜晚，两人在闹市中闲逛时，望着礼品店里精巧玲珑的各式玩偶，她突发奇想，问了 Eden这样的一个问题：有n个玩偶，每个玩偶有对应的价值、价钱，每个玩偶都可以被买有限次，在携带的价钱m固定的情况下，如何选择买哪些玩偶以及每个玩偶买多少个，才能使得选择的玩偶总价钱不超过m，且价值和最大。众所周知的，这是一个很经典的多重背包问题，Eden很快解决了，不过她似乎因为自己的问题被飞快解决感到了一丝不高兴，于是她希望把问题加难：多次 询问，每次询问都将给出新的总价钱，并且会去掉某个玩偶（即这个玩偶不能被选择），再问此时的多重背包的答案（即前一段所叙述的问题）。 这下Eden 犯难了，不过Eden不希望自己被难住，你能帮帮他么？ ###Input 第一行一个数n，表示有n个玩偶，玩偶从0开始编号 第二行开始后面的 n行，每行三个数 ai, bi, c i，分别表示买一个第i个玩偶需要的价钱，获得的价值以及第i个玩偶的限购次数。 接下来的一行为q，表示询问次数。 接下来q行，每行两个数di. ei表示每个询问去掉的是哪个玩偶（注意玩偶从0开始编号）以及该询问对应的新的总价钱数。（去掉操作不保留，即不同询问互相独立） ###Output 输出q行，第i行输出对于第 i个询问的答案。 ###Sample Input 5 2 3 4 1 2 1 4 1 2 2 1 1 3 2 3 5 1 10 2 7 3 4 4 8 0 5 ###Sample Output 13 11 6 12 4 ###Solution 多重背包+分治背包 递归处理[l,r)，每次加入左半部分的点，处理右边，再加入右边，处理左边 时间复杂度$$O(n^2log^2n+q)$$ ###Code ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define sqr(x) ((x)*(x)) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) struct _toy { int a,b,c; }toy[1000]; struct _qr { int w,ans,ne; }qr[300001]; int p[1000],n,q,f[11][1001]; inline void merge(int *s,int a,int b) { for(int i=1000;i>=a;i--) repr(s[i],max(s[i-1],s[i-a]+b)); } void solve(int l,int r,int d) { if(l+1==r) { for(int i=p[l];i;i=qr[i].ne) qr[i].ans=f[d][qr[i].w]; } else { int p=(l+r)>>1; memcpy(f[d+1],f[d],sizeof(f[d])); for(int i=l;i /archives/72/ 2016-11-09T16:51:00+08:00 ###Description 1946 年 3 月 5 日，英国前首相温斯顿·丘吉尔在美国富尔顿发表“铁幕演说”，正式拉开了冷战序幕。 美国和苏联同为世界上的“超级大国”，为了争夺世界霸权，两国及其盟国展开了数十年的斗争。在这段时期，虽然分歧和冲突严重，但双方都尽力避免世界范围的大规模战争（第三次世界大战）爆发，其对抗通常通过局部代理战争、科技和军备竞赛、太空竞争、外交竞争等“冷”方式进行，即“相互遏制，不动武力”，因此称之为“冷战”。 Reddington 是美国的海军上将。由于战争局势十分紧张，因此他需要时刻关注着苏联的各个活动，避免使自己的国家陷入困境。苏联在全球拥有 N 个军工厂，但由于规划不当，一开始这些军工厂之间是不存在铁路的，为了使武器制造更快，苏联决定修建若干条道路使得某些军工厂联通。 Reddington 得到了苏联的修建日程表，并且他需要时刻关注着某两个军工厂是否联通，以及最早在修建哪条道路时会联通。具体而言，现在总共有M 个操作，操作分为两类： • 0 u v，这次操作苏联会修建一条连接 u 号军工厂及 v 号军工厂的铁路，注意铁路都是双向的; • 1 u v， Reddington 需要知道 u 号军工厂及 v 号军工厂最早在加入第几条条铁路后会联通，假如到这次操作都没有联通，则输出 0; 作为美国最强科学家， Reddington 需要你帮忙设计一个程序，能满足 他的要求。 ###Input 第一行两个整数 N, M。 接下来 M 行，每行为 0 u v 或 1 u v 的形式。 数据是经过加密的，对于每次加边或询问，真正的 u, v 都等于读入的 u, v 异或上上一次询问的答案。一开始这个值为 0。 1 ≤ N, M ≤ 500000，解密后的 u, v 满足1 ≤ u, v ≤ N, u不等于v ###Output 对于每次 1 操作，输出 u, v 最早在加入哪条边后会联通，若到这个操 作时还没联通，则输出 0。 ###Sample Input 5 9 0 1 4 1 2 5 0 2 4 0 3 4 1 3 1 0 7 0 0 6 1 0 1 6 1 2 6 ###Sample Output ``` 0 3 5 ``` ###Solution 直接用LCT维护动态最小生成树就行了，虽然很暴力，但能AC ###Code ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; typedef long double ldb; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} template inline T gcd(T a,T b){if(b)return gcd(b,a%b);return a;} #define mp(a,b) std::make_pair(a,b) #define pb push_back #define lb(x) ((x)&(-(x))) #define pm(a,b,c,d) a=(a+(ll)(b)*(c))%(d) const int N=1000001; struct node { node *c[2],*fa; int val,ma; bool rev; inline void rotate(bool f); inline void pushdown(); inline void pushup(); }s[N],_null,*null=&_null; inline void node::pushdown() { if(fa->c[0]==this||fa->c[1]==this) fa->pushdown(); if(rev) { rev=0; std::swap(c[0],c[1]); if(c[0]!=null)c[0]->rev=!c[0]->rev; if(c[1]!=null)c[1]->rev=!c[1]->rev; } } inline void node::rotate(bool f) { fa->c[f]=c[!f]; c[!f]=fa; fa=c[!f]->fa; if(c[!f]->fa->c[1]==c[!f]) c[!f]->fa->c[1]=this; else if(c[!f]->fa->c[0]==c[!f]) c[!f]->fa->c[0]=this; c[!f]->fa=this; c[!f]->c[f]->fa=c[!f]; c[!f]->pushup(); } inline void node::pushup() { ma=val; if(c[0]!=null)repr(ma,c[0]->ma); if(c[1]!=null)repr(ma,c[1]->ma); } inline void init(node *x,int v) { x->val=v,x->c[0]=null,x->c[1]=null,x->fa=null; } inline void splay(node *a) { a->pushdown(); while(a->fa->c[0]==a||a->fa->c[1]==a) a->rotate(a==a->fa->c[1]); a->pushup(); } inline void access(node *a) { node *x=null; while(a!=null) { splay(a); a->c[1]=x; a->pushup(); x=a,a=a->fa; } } inline void movetoroot(node *x) { access(x); splay(x); x->rev=!x->rev; } inline void link(node *x,node *y) { movetoroot(x); x->fa=y; } inline void cut(node *x,node *y) { movetoroot(x); access(y); splay(y); x->fa=null; y->c[0]=null; y->pushup(); } inline void split(node *x,node *y) { movetoroot(x),access(y),splay(y); } inline node* findroot(node *x) { while(x->fa!=null) x=x->fa; return x; } int main() { int n,m,lstans=0,opt,x,y; scanf("%d%d",&n,&m); for(int i=1;i /archives/70/ 2016-11-09T12:55:00+08:00 ###Description XLk觉得《上帝造题的七分钟》不太过瘾，于是有了第二部。 "第一分钟，X说，要有数列，于是便给定了一个正整数数列。 第二分钟，L说，要能修改，于是便有了对一段数中每个数都开平方(下取整)的操作。 第三分钟，k说，要能查询，于是便有了求一段数的和的操作。 第四分钟，彩虹喵说，要是noip难度，于是便有了数据范围。 第五分钟，诗人说，要有韵律，于是便有了时间限制和内存限制。 第六分钟，和雪说，要省点事，于是便有了保证运算过程中及最终结果均不超过64位有符号整数类型的表示范围的限制。 第七分钟，这道题终于造完了，然而，造题的神牛们再也不想写这道题的程序了。" ——《上帝造题的七分钟·第二部》 所以这个神圣的任务就交给你了。 ###Input 第一行一个整数n，代表数列中数的个数。 第二行n个正整数，表示初始状态下数列中的数。 第三行一个整数m，表示有m次操作。 接下来m行每行三个整数k,l,r，k=0表示给[l,r]中的每个数开平方(下取整)，k=1表示询问[l,r]中各个数的和。 ###Output 对于询问操作，每行输出一个回答。 ###Sample Input 10 1 2 3 4 5 6 7 8 9 10 5 0 1 10 1 1 10 1 1 5 0 5 8 1 4 8 ###Sample Output 19 7 6 ###Solution 显然，一个数最多开根6次就会变成1 那么直接用线段树维护区间最大值，每次暴力修改即可 ###Code ```c++ #include typedef unsigned char uchar; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define xx first #define yy second template inline T max(T a,T b){return a>b?a:b;} template inline T min(T a,T b){return a0?a:-a;} template inline void repr(T &a,T b){if(ab)a=b;} #define mp(a,b) std::make_pair(a,b) #define pb push_back int n,t=1; ll s[270000],ma[270000]; inline void up(int x) { s[x]=s[x