当前位置：首页 > 范文大全 > 实用文>Codefoeces 387E George and Cards 贪心+线段树

Codefoeces 387E George and Cards 贪心+线段树

2022-12-05 08:25:22 收藏本文下载本文

“看起来好好吃”通过精心收集，向本站投稿了9篇Codefoeces 387E George and Cards 贪心+线段树，下面是小编为大家推荐的Codefoeces 387E George and Cards 贪心+线段树，欢迎阅读，希望大家能够喜欢。

篇1：Codefoeces 387E George and Cards 贪心+线段树

首先要知道每次拿走最小才会达到最优，因为最小的不会给其他的提供任何加分，只有可能减小加分，

删除卡片的次序确定了，剩下的就是确定每段区间的左右端点。

pos[i] 表示数字 i 在初始序列中的位置。

首先枚举i (i = 1 ->n)，如果不需删除，则将pos[i]放入setS中，如果不需删除，则在S中二分查找上下界。

总的时间复杂度为o( (n-k)*log(k) )。

#include #include#include#include#include#include#include#include#include#include#include#include#pragma comment(linker,“/STACK:1024000000”);#define EPS (1e-6)#define LL long long#define ULL unsigned long long#define INF 0x3f3f3f3f#define Mod 1000000007#define mod 1000000007/** I/O Accelerator Interface .. **/#define g (c=getchar)#define d isdigit(g)#define p x=x*10+c-'0'#define n x=x*10+'0'-c#define pp l/=10,p#define nn l/=10,ntemplateinline T& RD(T &x){ char c; while(!d); x=c-'0'; while(d)p; return x;}templateinline T& RDD(T &x){ char c; while(g,c!='-'&&!isdigit(c)); if (c=='-') { x='0'-g; while(d)n; } else { x=c-'0'; while(d)p; } return x;}inline double& RF(double &x)//scanf(“%lf”, &x);{ char c; while(g,c!='-'&&c!='.'&&!isdigit(c)); if(c=='-')if(g=='.') {x=0;double l=1;while(d)nn;x*=l; } else {x='0'-c;while(d)n;if(c=='.'){ double l=1; while(d)nn; x*=l;} } else if(c=='.') { x=0; double l=1; while(d)pp; x*=l; } else { x=c-'0'; while(d)p; if(c=='.') {double l=1;while(d)pp;x*=l; } } return x;}#undef nn#undef pp#undef n#undef p#undef d#undef gusing namespace std;int num[1000010];int pos[1000010];bool ap[1000010];int st[4001000];sets;int Init(int site,int l,int r){ if(l == r) return st[site] = 1; int mid = (l+r)>>1; return st[site] = Init(site<<1,l,mid) + Init(site<<1|1,mid+1,r);}int Query(int site,int L,int R,int l,int r){ if(L == l && R == r) return st[site]; int mid = (L+R)>>1; if(r<= mid) return Query(site<<1,L,mid,l,r); if(mid< l) return Query(site<<1|1,mid+1,R,l,r); return Query(site<<1,L,mid,l,mid) + Query(site<<1|1,mid+1,R,mid+1,r);}void Update(int site,int l,int r,int x){ if(l == r) { st[site] = 0; return ; } int mid = (l+r)>>1; if(x<= mid) Update(site<<1,l,mid,x); else Update(site<<1|1,mid+1,r,x); st[site] = st[site<<1] + st[site<<1|1];}int main(){ int n,k,i,j,x; scanf(“%d %d”,&n,&k); for(i = 1;i<= n; ++i) scanf(“%d”,&num[i]),pos[num[i]] = i; memset(ap,false,sizeof(ap)); for(i = 1;i<= k; ++i) scanf(“%d”,&x),ap[x] = true; set::iterator it; LL sum = 0; Init(1,1,n); s.insert(n+1); s.insert(0); for(i = 1;i<= n; ++i) { if(ap[i]) {s.insert(pos[i]);continue; } it = s.upper_bound(pos[i]); int r = *it-1; int l = *(--it)+1; sum += Query(1,1,n,l,r); Update(1,1,n,pos[i]); } cout<

篇2：树状数组和线段树

一、树状数组

在解题过程中，我们有时需要维护一个数组的前缀和 S[i]=A[1]+A[2]+...+A[i] ，但是不难发现，如果我们修改了任意一个 A[i],S[i] 、S[i+1]...S[n] 都会发生变化。可以说，每次修改 A[i] 后，调整前缀和 S[] 在最坏情况下会需要 O(n) 的时间。当 n 非常大时，程序会运行得非常缓慢。因此，这里我们引入“树状数组”，它的修改与求和都是 O(logn) 的，效率非常高。

实现：

对于正整数x，定义lowbit（x）为x的二进制表达式中最右边的1所对应的值。

Lowbit(x)=x and -x对于节点i，如果它是左子节点，其父节点为i+lowbit(i)；

构造一个辅助数组C，其中Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+…+Ai即C的每个元素都是A数组中的一段连续和。具体是每个灰色节点i都属于一个以它自身结尾的水平长条，这个长条中的数之和就是Ci。如C12=A9+A10+A11+A12=C10+A11+A12

如何更新C数组中的元素：如果修改了一个Ai，需要更新C数组中的哪些元素呢？从Ci开始往右走，边走边“往上爬”（不一定沿着树中的边爬），沿途修改所有结点对应的Ci即可。预处理时先把C数组清空，然后执行n次add操作。总时间为O（nlogn）

如何计算前缀和Si：顺着结点i往左走，边走边“往上爬”（不一定沿着树中的边爬），把沿途经过的Ci累加起来就可以了。对于query（L,R）=SR-SL-1。

代码：

var

b,c,f:array [0..100000] of longint;

ff,a:Array [0..100000] of boolean;

i,j,m,n,x,y,ans,l,r,tmp:longint;

s:string;

function dfs(x:longint):longint;

begin

if x<=1 then

exit;

c[f[x]]:=c[f[x]]+c[x];

dfs(f[x]);

end;

procedure dfs1(x:longint);

begin

dec(c[x]);

if x<=1 then

exit;

dfs1(f[x]);

end;

procedure dfs2(x:longint);

begin

inc(c[x]);

if x<=1 then

exit;

dfs2(f[x]);

end;

begin

readln(n);

fillchar(ff,sizeof(ff),true);

for i:=1 to n-1 do

begin

readln(x,y);

f[y]:=x;

inc(b[x]);

end;

for i:=1 to n do

c[i]:=1;

for i:=1 to n do

begin

if b[i]=0 then

dfs(i);

end;

readln(m);

for i:=1 to m do

begin

x:=0;

readln(s);

if s[1]='Q' then

begin

for j:=3 to length(s) do

x:=x*10+ord(s[j])-ord('0');

writeln(c[x]);

end;

if s[1]='C' then

begin

for j:=3 to length(s) do

x:=x*10+ord(s[j])-ord('0');

if ff[x] then

dfs1(x) else

dfs2(x);

ff[x]:=not ff[x];

end;

End.

二、线段树

1,.线段树的结构:

区间：用一对数a和b表示一个前闭后开的区间[a,b)。（可以自己修改）结点T(a,b)：表示该结点维护了原数列中区间[a,b)的信息，其中a和b为整数且a1，那么T(a,(a+b)/2)为T(a,b)的左孩子结点，T((a+b)/2,b)为T(a,b)的右孩子

叶结点：如果对于结点T(a,b)，有b-a=1，那么该结点就是叶结点线段树结构是递归定义的。

2.线段树的性质:

结点数：假设该线段树处理的数列长度为n，即根结点的区间为[1,n+1)，那么总结点个数不超过2*n个。深度：线段树可以近似看做一棵满二叉树，所以深度不超过log（2*n）线段分解数量级：线段树把区间上的任意一条长度为L的线段都分成了不超过2logL条线段，这使得大多数查询能够在O（logn）的时间内解决。

线段树的存储：

1、链表存储

2、数组模拟链表

3、堆结构存储

应用：

忠诚（loyal）

【问题描述】

老管家是一个聪明能干的人，

他为财主工作了整整，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。

在询问过程中账本的内容可能会被修改

【输入格式】

输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。

接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y

当p=1 则查询x,y区间

当p=2 则改变第x个数为y

【输出格式】

输出文件中为每个问题的答案。具体查看样例。

【输入样例】

10 3

1 2 3 4 5 6 7 8 9 10

1 2 7

2 2 0

1 1 10

【输出样例】

2 0

代码：

type

point=^node;

node=record

left,right:longint;

lp,rp:point;

sum:longint;

end;

var

p:array [1..100000] of node;

i,j,m,n,x,y,k:longint;

a:array [1..100000] of longint;

root:point;

procedure creat(p:point;l,r:longint);

begin

p^.left:=l; p^.right:=r; p^.sum:=maxlongint;

if l+1=r then

begin

p^.lp:=nil;

p^.rp:=nil;

end

else

begin

new(p^.lp); creat(p^.lp,l,(l+r) div 2);

new(p^.rp); creat(p^.rp,(l+r) div 2,r);

end;

function min(x,y:longint):longint;

begin

if x

exit(x);

exit(y);

end;

procedure update(p:point;x,delta:longint);

begin

if p^.left+1=p^.right then

begin

p^.sum:=delta;

end

else

begin

if x<(p^.left+p^.right) div 2 then

update(p^.lp,x,delta);

if x>=(p^.left+p^.right) div 2 then

update(p^.rp,x,delta);

p^.sum:=min(p^.lp^.sum,p^.rp^.sum);

end;

function query(p:point;l,r:longint):longint;

var

ans:longint;

begin

if (l<=p^.left) and (p^.right<=r) then

exit(p^.sum);

ans:=maxlongint;

if l<(p^.left+p^.right) div 2 then

ans:=min(ans,query(p^.lp,l,r));

if r>(p^.left+p^.right) div 2 then

ans:=min(ans,query(p^.rp,l,r));

exit(ans);

end;

begin

readln(n,m);

for i:=1 to n do

read(a[i]);

new(root);

creat(root,1,n+1);

for i:=1 to n do

update(root,i,a[i]);

for i:=1 to m do

begin

readln(k,x,y);

if k=2 then

update(root,x,y);

if k=1 then

write(query(root,x,y+1),' ');

end;

writeln;

End.

篇3：hdu1754 I hate it （线段树）

I Hate It

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 55291 Accepted Submission(s): 21599

Problem Description 很多学校流行一种比较的习惯，老师们很喜欢询问，从某某到某某当中，分数最高的是多少。

这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input 本题目包含多组测试，请处理到文件结束。

在每个测试的第一行，有两个正整数 N 和 M ( 0<=00,0<5000 br=“”>学生ID编号分别从1编到N。

第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。

接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。

当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。

当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。

Output 对于每一次询问操作，在一行里面输出最高成绩。

Sample Input

5 61 2 3 4 5Q 1 5U 3 6Q 3 4Q 4 5U 2 9Q 1 5

Sample Output

5659HintHuge input,the C function scanf will work better than cin

Author linle

分析：线段树入门基础题，每次更新结点存储该以结点为根的子树中最大值。

#include#include#include#include#include#include#include#include#include#include using namespace std;const double eps = 1e-6;const double pi = acos(-1.0);const int INF = 0x3f3f3f3f;const int MOD = 1000000007;#define ll long long#define CL(a,b) memset(a,b,sizeof(a))#define MAXN 800010struct node{ int a,b,r;}t[MAXN];int n,m,ans;void build(int x, int y, int num){ t[num].a = x; t[num].b = y; t[num].r = 0; if(x == y) return ; int mid = (x+y)/2; build(x, mid, num*2); build(mid+1, y, num*2+1);}void update(int x, int y, int num){ if (t[num].a == t[num].b && t[num].b == x) { t[num].r = y; return ; } int mid = (t[num].a+t[num].b)/2; if(x >mid) update(x, y, num*2+1); else update(x, y, num*2); t[num].r = max(t[num*2].r, t[num*2+1].r);}void query(int x, int y, int num){ if(t[num].a == x && t[num].b == y) { ans = max(ans, t[num].r); return ; } int mid = (t[num].a+t[num].b)/2; if(x >= mid+1) query(x, y, num*2+1); else if(y <= mid) query(x, y, num*2); else { query(x, mid, num*2); query(mid+1, y, num*2+1); }}int main(){ char ch; int x,y,k; while(scanf(“%d%d”,&n,&m)==2) { build(1, n, 1); for(int i=1; i<=n; i++) {scanf(“%d”,&k);update(i, k, 1); } while(m--) {getchar();scanf(“%c%d%d”,&ch,&x,&y);if(ch == 'U'){ update(x, y, 1);}else if(ch == 'Q'){ ans = -99999; query(x, y, 1); printf(“%d\n”,ans);} } } return 0;}

<=200000,0<5000>

篇4：HDU 2795 Billboard（简单线段树）

Billboard

Time Limit: 20000/8000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 12812 Accepted Submission(s): 5578

Problem Description At the entrance to the university, there is a huge rectangular billboard of size h*w (h is its height and w is its width). The board is the place where all possible announcements are posted: nearest programming competitions, changes in the dining room menu, and other important information.

On September 1, the billboard was empty. One by one, the announcements started being put on the billboard.

Each announcement is a stripe of paper of unit height. More specifically, the i-th announcement is a rectangle of size 1 * wi.

When someone puts a new announcement on the billboard, she would always choose the topmost possible position for the announcement. Among all possible topmost positions she would always choose the leftmost one.

If there is no valid location for a new announcement, it is not put on the billboard (that's why some programming contests have no participants from this university).

Given the sizes of the billboard and the announcements, your task is to find the numbers of rows in which the announcements are placed.

Input There are multiple cases (no more than 40 cases).

The first line of the input file contains three integer numbers, h, w, and n (1 <= h,w <= 10^9; 1 <= n <= 200,000) - the dimensions of the billboard and the number of announcements.

Each of the next n lines contains an integer number wi (1 <= wi <= 10^9) - the width of i-th announcement.

Output For each announcement (in the order they are given in the input file) output one number - the number of the row in which this announcement is placed. Rows are numbered from 1 to h, starting with the top row. If an announcement can't be put on the billboard, output “-1” for this announcement.

Sample Input

3 5 524333

Sample Output

1213-1

Author hhanger@zju

Source HDOJ Summer Exercise（5）

Recommend lcy | We have carefully selected several similar problems for you: 1698 1542 1828 1540 2871

题意：有一个h*w的木板，要在上面贴广告，有一个要求就是尽可能的贴在上面，如果不能就尽可能的贴在左面，（这样可以使得贴的广告数目最多吧），每个广告都是1*wi，这就说明每一个广告只能占据一行，可以使用线段树进行维护，每次都进行比较，如果最上面剩下的宽度大于或等于广告的宽就减去广告在木板该行的宽度，

HDU 2795 Billboard（简单线段树）

，

如果能想起来这种方法就很简单，如果想不出来都不知道怎么做...

#include#include#include#include#include#include#includeusing namespace std;const int maxn = 200001;struct node{ int l; int r; int cnt;}q[maxn<<4];int h,w,n;void build(int l,int r,int rt){ q[rt].l = l; q[rt].r = r; q[rt].cnt = 0; if(q[rt].l == q[rt].r) { q[rt].cnt = w; return ; } int mid = (l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); q[rt].cnt = max(q[rt<<1].cnt,q[rt<<1|1].cnt);}int qurry(int k,int l,int r,int rt){ if(q[rt].l == q[rt].r) { q[rt].cnt -= k; return q[rt].l; } int mid = (l+r)>>1; int ans = 0; if(q[rt<<1].cnt>=k) { ans = qurry(k,l,mid,rt<<1); } else { ans = qurry(k,mid+1,r,rt<<1|1); } q[rt].cnt = max(q[rt<<1].cnt,q[rt<<1|1].cnt); return ans;}int main(){ while(scanf(“%d%d%d”,&h,&w,&n)!=EOF) { if(h>n) {h = n; } build(1,h,1); while(n--) {int m;scanf(“%d”,&m);if(m>q[1].cnt){ printf(“-1\n”);}else{ int ans = qurry(m,1,h,1); printf(“%d\n”,ans);} } } return 0;}

篇5：hdu1166 敌兵布阵（线段树）

敌兵布阵

Time Limit: /1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 64143 Accepted Submission(s): 27036

Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了，A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。

中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:“你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说：”我知错了。。。“但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.

Input 第一行一个整数T，表示有T组数据。

每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。

接下来每行有一条命令，命令有4种形式：

(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）

(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;

(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;

(4)End 表示结束，这条命令在每组数据最后出现;

每组数据最多有40000条命令

Output 对第i组数据,首先输出“Case i:”和回车,

对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。

Sample Input

1101 2 3 4 5 6 7 8 9 10Query 1 3Add 3 6Query 2 7Sub 10 2Add 6 3Query 3 10End

Sample Output

Case 1:63359

Author Windbreaker

分析：最基础的线段树入门题，属于模板题，每次更新节点就行了。

#include#include#include#include#include#include#include#include#include#include using namespace std;const double eps = 1e-6;const double pi = acos(-1.0);const int INF = 0x3f3f3f3f;const int MOD = 1000000007;#define ll long long#define CL(a,b) memset(a,b,sizeof(a))#define MAXN 100010struct node{ int a,b,sum;}t[400010];int ans, r[500010];void build(int x, int y, int num){ t[num].a = x; t[num].b = y; if(x == y) t[num].sum = r[y]; else { int mid = (x+y)/2; build(x, mid, num*2); build(mid+1, y, num*2+1); t[num].sum = t[num*2].sum + t[num*2+1].sum; }}void add(int x, int y, int num){ if(t[num].a == x && t[num].b == x) { t[num].sum += y; return ; } int mid = (t[num].a+t[num].b)/2; if(x >mid) add(x, y, num*2+1); else add(x, y, num*2); t[num].sum = t[num*2].sum + t[num*2+1].sum;}void sub(int x, int y, int num){ if(t[num].a == x && t[num].b == x) { t[num].sum -= y; return ; } int mid = (t[num].a+t[num].b)/2; if(x >mid) sub(x, y, num*2+1); else sub(x, y, num*2); t[num].sum = t[num*2].sum + t[num*2+1].sum;}void query(int x, int y, int num){ if(t[num].a == x && t[num].b == y) { ans += t[num].sum; return ; } int mid = (t[num].a+t[num].b)/2; if(y <= mid) query(x, y, num*2); else if(x >= mid+1) query(x, y, num*2+1); else { query(x, mid, num*2); query(mid+1, y, num*2+1); }}int main{ int T,n; char str[6]; scanf(”%d“,&T); for(int cas=1; cas<=T; cas++) { int x,y; scanf(”%d“,&n); r[0] = 0; for(int i=1; i<=n; i++)scanf(”%d“,&r[i]); build(1, n, 1); printf(”Case %d:\n“,cas); while(scanf(”%s“,str)==1) {//scanf(”%d%d“,&x,&y);if(strcmp(str, ”End“)==0) break;else if(strcmp(str, ”Add“)==0){ scanf(”%d%d“,&x,&y); add(x, y, 1);}else if(strcmp(str, ”Sub“)==0){ scanf(”%d%d“,&x,&y); sub(x, y, 1);}else if(strcmp(str, ”Query“)==0){ scanf(”%d%d“,&x,&y); ans = 0; query(x, y, 1); printf(”%d\n“,ans);} } } return 0;}

篇6：hdu 3973 字符串hash+线段树

Problem Description You are given some words {Wi}. Then our stupid AC will give you a very long string S. AC is stupid and always wants to know whether one substring from S exists in the given words {Wi} .

For example, S = abcd, and the given words {Wi} = {bc, ad, dd}. Then Only S[2..3] = bc exists in the given words. (In this problem, the first element of S has the index 0.)

However, this is toooooooooooo easy for acmers ! The stupid and evil AC will now change some letters in S. So could you solve this problem now?

Input The first line is one integer T indicates the number of the test cases. (T <=20)

Then for every case, there is one integer n in the first line indicates the number of the given words(The size of the {Wi}) . Then n lines has one string which only has 'a'- 'z'. (1 <= n <= 10000, sigma|Wi| <= 2000000) .

Then one line has one string S, here |S| <= 100000.

Then one integer m, indicating the number of operations. (1 <= m <= 100000)

Then m lines , each line is the operation:

(1)Q L R , tell AC whether the S[L..R] exists in the given strings ;

(2)C X Y , chang S[X] to Y, here Y : 'a'-'z' .www.2cto.com

Output First output “Case #idx:” in a single line, here idx is the case number count from 1.Then for each Q operation, output Yes if S[L..R] exists in the given strings, otherwise output No.

Sample Input

12ab ioc ipcad 6 Q 0 2 Q 3 4 C 1 o C 4 b Q 0 2 Q 3 4

Sample Output

Case #1:NoNo Yes Yes

/**hdu 3973 线段树单点更新区间求值+字符串hash题目大意：给定多个字符串，然后给定一个大串，对该串进行单点更新和区间查询，查询的区间子串是不是在已知的字符串中出现解题思路：对字符串进行hash处理采用线段树来进行更新，用set存放字符串的哈希值，

hdu 3973 字符串hash+线段树

，至于怎么哈希和大白书上的思路差不多只是这里是表示的前缀*/#include#include#include#includeusing namespace std;const int maxn=100010;const int seed=31;typedef unsigned long long LL;struct note{ int l,r; LL hashes;}tree[maxn*4];char str[2000100];LL Hash[maxn];int n;void init(){ Hash[0]=1; for(int i=1;i>1; if(l<=mid) update(l,root<<1); else update(l,root<<1|1); tree[root].hashes=tree[root<<1].hashes*Hash[tree[root].r-mid]+tree[root<<1|1].hashes;}LL query(int l,int r,int root){ // printf(**); if(tree[root].l==l&&tree[root].r==r) return tree[root].hashes; int mid=(tree[root].r+tree[root].l)>>1; if(r<=mid)return query(l,r,root<<1); else if(l>mid)return query(l,r,root<<1|1); return query(l,mid,root<<1)*Hash[r-mid]+query(mid+1,r,root<<1|1);}int main(){ int T,tt=0; init(); scanf(%d,&T); while(T--) { printf(Case #%d:,++tt); scanf(%d,&n); setmp; for(int i=0;i

篇7：poj 2828 线段树插孔处理

给你一个数列出现的先后顺序num【i】和对应数值输出最后排好序的对应数值，如

40 771 511 332 69第一步 77

第二部 77 51

第三步 77 33 51

第四部77 33 69 51

后面先出现的位置是固定的所以从后往前处理，线段树每个节点存当前区间还有多少个空位；

#include#include#includeusing namespace std;#define LL(x) (x<<1)#define RR(x) ((x<<1)|1)struct node { int cont;}tree[4*00];int num[200010][3],queue[200010];int deal(int L,int R,int point){ tree[point].cont=R-L+1; if(L==R)return 0; int mid=(L+R)/2; deal(L,mid,LL(point)); deal(mid+1,R,RR(point)); return 0; }int update(int L,int R,int pos,int point,int value){ tree[point].cont--; if(L==R) { queue[L]=value; return 0; } int mid=(L+R)/2; if(pos<=tree[LL(point)].cont) update(L,mid,pos,LL(point),value); else update(mid+1,R,pos-tree[LL(point)].cont,RR(point),value); return 0;}int main{ int n,i,j; while(~scanf(”%d“,&n)) { deal(1,n,1); for(i=1;i<=n;i++) { scanf(”%d%d“,&num[i][1],&num[i][2]); num[i][1]++; } for(i=n;i>=1;i--) {update(1,n,num[i][1],1,num[i][2]); } for(i=1;i<=n;i++) { if(i!=1) printf(” “); printf(”%d“,queue[i]); } printf(”\n“); } return 0;}

篇8：hdu4267A Simple Problem with Integers(线段树)

Problem Description

Let A1, A2, … , AN be N elements. You need to deal with two kinds of operations. One type of operation is to add a given number to a few numbers in a given interval. The other is to query the value of some element.

Input

There are a lot of test cases.

The first line contains an integer N. (1<= N<= 50000)

The second line contains N numbers which are the initial values of A1, A2, … , AN. (-10,000,000<= the initial value of Ai<= 10,000,000)

The third line contains an integer Q. (1<= Q<= 50000)

Each of the following Q lines represents an operation.

“1 a b k c” means adding c to each of Ai which satisfies a<= i<= b and (i - a) % k == 0. (1<= a<= b<= N, 1<= k<= 10, -1,000<= c<= 1,000)

“2 a” means querying the value of Aa. (1<= a<= N)

Output

For each test case, output several lines to answer all query operations.

Sample Input

4 1 1 1 1 14 2 1 2 2 2 3 2 4 1 2 3 1 2 2 1 2 2 2 3 2 4 1 1 4 2 1 2 1 2 2 2 3 2 4

Sample Output

1 1 1 1 1 3 3 1 2 3 4 1

Source

ACM/ICPC Asia Regional Changchun Online

Recommend

liuyiding | We have carefully selected several similar problems for you: 4276 4274 4273 4272 4270

k<=10, 模k为b的情况一共是55种,所以维护55颗线段树(或者说55个延迟标记)即可,内存卡的有点紧.

/************************************************************************* >File Name: hdu4267.cpp >Author: ALex >Mail: zchao1995@gmail.com >Created Time: 02月25日星期三 18时37分15秒 ************************************************************************/#include#include#include#include#include#include#include#include#include#include#include using namespace std;const double pi = acos(-1);const int inf = 0x3f3f3f3f;const double eps = 1e-15;typedef long long LL;typedef pairPLL;const int N = 50005;struct node{ int l, r; int sum; int add[55];}tree[N<< 2];void build (int p, int l, int r){ tree[p].l = l; tree[p].r = r; for (int i = 0; i< 55; ++i) { tree[p].add[i] = 0; } if (l == r) { scanf(”%d“, &tree[p].sum); return; } int mid = (l + r) >>1; build (p<< 1, l, mid); build (p<< 1 | 1, mid + 1, r); tree[p].sum = tree[p<< 1].sum + tree[p<< 1 | 1].sum;}void pushdown (int p){ int k = 1; int b = -1; for (int i = 1; i<= 55; ++i) { if (i >(2 * k + (k - 1) * (k - 2) / 2 - 1)) {++k;b = 0; } else {++b; } if (tree[p].add[i - 1]) {tree[p<< 1].add[i - 1] += tree[p].add[i - 1];tree[p<< 1 | 1].add[i - 1] += tree[p].add[i - 1];int m = (tree[p<< 1].r - b) / k + 1;if (tree[p<< 1].l - 1 - b >= 0){ m -= (tree[p<< 1].l - 1 - b) / k + 1;}tree[p<< 1].sum += m * tree[p].add[i - 1];// printf(”区间[%d,%d] 模%d为%d的有%d个\n“, tree[p<< 1].l, tree[p<< 1].r, k, b, m);m = (tree[p<< 1 | 1].r - b) / k + 1;if ((tree[p<< 1 | 1].l - 1 - b) >= 0){ m -= (tree[p<< 1 | 1].l - 1 - b) / k + 1;}tree[p<< 1 | 1].sum += m * tree[p].add[i - 1];tree[p].add[i - 1] = 0;// printf(”区间[%d, %d] 模%d为%d的有%d个\n“, tree[p<< 1 | 1].l, tree[p<< 1 | 1].r, k, b, m); } }}void update (int p, int l, int r, int k, int b, int c){ if (l == tree[p].l && tree[p].r == r) { int m = (tree[p].r - b) / k + 1; if (tree[p].l - 1 - b >= 0) {m -= (tree[p].l - 1 - b) / k + 1; } tree[p].sum += m * c; int id = k + (k - 1) * (k - 2) / 2 + b - 1; tree[p].add[id] += c;//printf(”区间[%d, %d]模%d为%d的有%d个\n“, l, r, k, b, m); return; } pushdown (p); int mid = (tree[p].l + tree[p].r) >>1; if (r<= mid) { update (p<< 1, l, r, k, b, c); } else if (l >mid) { update (p<< 1 | 1, l, r, k, b, c); } else { update (p<< 1, l, mid, k, b, c); update (p<< 1 | 1, mid + 1, r, k, b, c); } tree[p].sum = tree[p<< 1].sum + tree[p<< 1 | 1].sum;}int query (int p, int pos){ if (tree[p].l == tree[p].r) { return tree[p].sum; } int mid = (tree[p].l + tree[p].r) >>1; pushdown (p); if (pos<= mid) { return query (p<< 1, pos); } else { return query (p<< 1 | 1, pos); }}int main (){ int n; while (~scanf(”%d“, &n)) { build (1, 1, n); int m; int op, l, r, k, c; scanf(”%d“, &m); while (m--) {scanf(”%d“, &op);if (op == 2){ scanf(”%d“, &l); printf(”%d\n“, query (1, l));}else{ scanf(”%d%d%d%d“, &l, &r, &k, &c); update (1, l, r, k, l % k, c);} } } return 0;}

篇9：线段树区间更新 HDU 3911

Black And White

Time Limit: 9000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 3811 Accepted Submission(s): 1129

Problem DescriptionThere are a bunch of stones on the beach; Stone color is white or black. Little Sheep has a magic brush, she can change the color of a continuous stone, black to white, white to black. Little Sheep like black very much, so she want to know the longest period of consecutive black stones in a range [i, j].

Input There are multiple cases, the first line of each case is an integer n(1<= n<= 10^5), followed by n integer 1 or 0(1 indicates black stone and 0 indicates white stone), then is an integer M(1<=M<=10^5) followed by M operations formatted as x i j(x = 0 or 1) , x=1 means change the color of stones in range[i,j], and x=0 means ask the longest period of consecutive black stones in range[i,j]

OutputWhen x=0 output a number means the longest length of black stones in range [i,j].

Sample Input

41 0 1 050 1 41 2 30 1 41 3 30 4 4

Sample Output

120

Source2011 Multi-University Training Contest 8 - Host by HUST 裸裸的区间更新，注意点已在代码中写出

#include#include#include#include#include#include #includeusing namespace std;#define MAXN 100000 + 1000struct node{ int lsum0,rsum0,msum0,lsum1,rsum1,msum1; int ck; int l,r; int mid(){ return (l+r)>>1; }}tree[MAXN<<2];int a[MAXN];void PushUp(int rt){ int ll = tree[rt<<1].r-tree[rt<<1].l+1;//左子树区间的长度 int rr = tree[rt<<1|1].r-tree[rt<<1|1].l+1;//右子树区间的长度 tree[rt].lsum1 = tree[rt<<1].lsum1; if(tree[rt<<1].lsum1 == ll){ tree[rt].lsum1 = tree[rt].lsum1+tree[rt<<1|1].lsum1; } tree[rt].rsum1 = tree[rt<<1|1].rsum1; if(tree[rt<<1|1].rsum1 == rr){ tree[rt].rsum1 = tree[rt].rsum1+tree[rt<<1].rsum1; } tree[rt].lsum0 = tree[rt<<1].lsum0; if(tree[rt<<1].lsum0 == ll){ tree[rt].lsum0+=tree[rt<<1|1].lsum0; } tree[rt].rsum0 = tree[rt<<1|1].rsum0; if(tree[rt<<1|1].rsum0 == rr){ tree[rt].rsum0+=tree[rt<<1].rsum0; } tree[rt].msum0=max(max(tree[rt<<1].msum0,tree[rt<<1|1].msum0),tree[rt<<1].rsum0+tree[rt<<1|1].lsum0); tree[rt].msum1 = max(max(tree[rt<<1].msum1,tree[rt<<1|1].msum1),tree[rt<<1].rsum1+tree[rt<<1|1].lsum1);}void PushDown(int rt){ if(tree[rt].ck == 1){ tree[rt<<1].ck ^= 1;//现在左子树父亲节点的所有01都需要交换，所以左子树也是需要交换，那么左子树的左右子树也是需要交换，如果原来左子树就要交换 tree[rt<<1|1].ck ^= 1;//，那么交换了两次就相当于不需要交换，这样异或之后就可以不需要交换 tree[rt].ck = 0; swap(tree[rt<<1].lsum0,tree[rt<<1].lsum1); swap(tree[rt<<1].rsum0,tree[rt<<1].rsum1); swap(tree[rt<<1].msum0,tree[rt<<1].msum1); swap(tree[rt<<1|1].lsum0,tree[rt<<1|1].lsum1); swap(tree[rt<<1|1].rsum0,tree[rt<<1|1].rsum1); swap(tree[rt<<1|1].msum0,tree[rt<<1|1].msum1); }}void build(int l,int r,int rt){ tree[rt].l = l; tree[rt].r = r; tree[rt].ck = 0;//开始的时候都不转换 if(l == r){ if(a[l] == 0){tree[rt].lsum0=tree[rt].rsum0=tree[rt].msum0=1;tree[rt].lsum1=tree[rt].rsum1=tree[rt].msum1=0; } else{tree[rt].lsum1=tree[rt].rsum1=tree[rt].msum1=1;tree[rt].lsum0=tree[rt].rsum0=tree[rt].msum0=0; } return ; } //int m = (l+r)>>1; int m = tree[rt].mid(); build(l,m,rt<<1); build(m+1,r,rt<<1|1); PushUp(rt);}void update(int l,int r,int rt){ if(l<=tree[rt].l && tree[rt].r<=r){ tree[rt].ck ^= 1; swap(tree[rt].lsum0,tree[rt].lsum1); swap(tree[rt].rsum0,tree[rt].rsum1); swap(tree[rt].msum0,tree[rt].msum1); return ; } PushDown(rt); int m = tree[rt].mid(); if(r<= m){ update(l,r,rt<<1); } else if(l >m){ update(l,r,rt<<1|1); } else{ update(l,m,rt<<1); update(m+1,r,rt<<1|1); } PushUp(rt);}int query(int l,int r,int rt){ if(l<=tree[rt].l && tree[rt].r<=r){ return tree[rt].msum1; } PushDown(rt); int m = tree[rt].mid(); if(r<= m){ return query(l,r,rt<<1); } else if(l >m){ return query(l,r,rt<<1|1); } else{ int lr = query(l,m,rt<<1); int rr = query(m+1,r,rt<<1|1); int a = tree[rt<<1].rsum1;//左子树最长的连续的1 if(a >tree[rt<<1].r-l+1){//后面的那个是最大范围a = tree[rt<<1].r-l+1; } int b = tree[rt<<1|1].lsum1; if(b >r-tree[rt<<1|1].l+1){b = r-tree[rt<<1|1].l+1; } return max(max(lr,rr),a+b); }}int main(){ int i; int n,m,op,aa,b; while(~scanf(”%d“,&n)){ for(i=1;i<=n;i++){scanf(”%d“,&a[i]); } build(1,n,1); scanf(”%d“,&m); while(m--){scanf(”%d%d%d“,&op,&aa,&b);if(op == 0){ int ans = query(aa,b,1); printf(”%d\n",ans);}else{ update(aa,b,1);} } } return 0;}

【Codefoeces 387E George and Cards 贪心+线段树】相关文章：

1.HDU 3911 Black And White（线段树区间合并）