/category/seg/ /archives/149/ 2016-12-16T15:59:00+08:00 ###Description 小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，其中1=k)return kth(s[a].lc,s[b].lc,l,f,k); return kth(s[a].rc,s[b].rc,f+1,r,k-t); } int root[N+1]; } int n,m,q; namespace t1 { int p[N+1],idm,id[N+1],idr[N+1],fa[N+1][17],dep[N+1],sz[N+1]; struct edge { int to,ne; }e[N /archives/90/ 2016-12-01T20:46:00+08:00 ###Description 敌方有n台人形兵器，每台的攻击力为Ai，护甲值为Di。我方只有一台人形兵器，攻击力为ATK。战斗看作回合制， 每回合进程如下： ·1 我方选择对方某台人形兵器并攻击，令其护甲值减少ATK，若护甲值 /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/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 /archives/31/ 2016-09-15T13:11:00+08:00 ###Description 老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。 ###Input 第一行两个整数N和P(1≤P≤1000000000）。第二行含有N个非负整数,从左到右依次为a1,a2,…,aN, (0≤ai≤1000000000,1≤i≤N)。第三行有一个整数M，表示操作总数。从第四行开始每行描述一个操作，输入的操作有以下三种形式： 操作1：“1 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai×c (1≤t≤g≤N,0≤c≤1000000000)。 操作2：“2 t g c”(不含双引号)。表示把所有满足t≤i≤g的ai改为ai+c (1≤t≤g≤N,0≤c≤1000000000)。 操作3：“3 t g”(不含双引号)。询问所有满足t≤i≤g的ai的和模P的值 (1≤t≤g≤N)。 同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。 ###Output 对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。 ###Sample Input 7 43 1 2 3 4 5 6 7 5 1 2 5 5 3 2 4 2 3 7 9 3 1 3 3 4 7 ###Sample Output 2 35 8 ###Solution 很显然，这是一道线段树区间修改+区间查询的裸题，每个节点存两个tag，分别表示乘多少，加多少，对于加的操作直接处理，乘的操作两个tag都乘 ###Code ```c++ #include #define LL long long int seg[270000],t=1,f=0,t1[270000],t2[270000]={0},p,ys[270000]; bool tag[270000]; inline int se(int x) { if(tag[x]) return ((LL)seg[x]*t1[x]+(LL)t2[x]*ys[x])%p; else return seg[x]; } inline void pd(int x) { if(tag[x]) { t1[x