敌兵布阵

电玩女神 2022-08-03 05:08 141阅读 0赞

线段树:

<pre name="code" class="cpp">#include <stdio.h>
    #include <string.h>
    int a[1000000],n;
    int sum(int x,int y)
    {
    	return x+y;
    }
    void build(int l,int r,int rt)
    {
    	if(l == r)
    	{
    		scanf("%d",&a[rt]);
    		return ;
    	}
    	int m = (l + r) >> 1;
    	build(l,m,rt<<1);
    	build(m+1,r,(rt<<1)+1);
    	//a[rt] = sum(a[rt<<1],a[(rt<<1)+1]);
    }
    
    void update(int l,int r,int p,int q,int rt)
    {
    	if(l == r)
    	{
    		a[rt] += q;
    		return;
    	}
    	int m = (l + r) >> 1;
    	if(p <= m)
    		update(l,m,p,q,rt<<1);
    	else
    		update(m+1,r,p,q,(rt<<1)+1);
    	//a[rt] = sum(a[rt<<1],a[(rt<<1)+1]);
    }
    
    int query(int l,int r,int p,int q,int rt)
    {
    	if(p <= l && q >= r)
    	{
    		return a[rt];
    	}
    	int ret = 0;
    	int m = (l + r) >> 1;
    	if(p <= m)
    	{
    		ret += query(l,m,p,q,rt<<1);
    	}
    	if(q > m)
    	{
    		ret += query(m+1,r,p,q,(rt<<1)+1);
    	}
    	return ret;
    }
    int main()
    {
    	int t,x,y,cas = 1;
    	scanf("%d",&t);
    	char a[10];
    	while(t--)
    	{
    		printf("Case %d:\n",cas++);
    		scanf("%d",&n);
    		build(1,n,1);
    		while(scanf("%s",a),strcmp(a,"End"))
    		{
    			if(strcmp(a,"Query") == 0)
    			{
    				scanf("%d %d",&x,&y);
    				printf("%d\n",query(1,n,x,y,1));
    			}
    			else
    			{
    				scanf("%d %d",&x,&y);
    				if(strcmp(a,"Add")==0)
    					update(1,n,x,y,1);
    				else
    					update(1,n,x,-y,1);
    			}
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关【杭电oj1166】敌兵布阵

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

末蓝、/ 2022年09月25日 07:28/ 0 赞/ 87 阅读

相关 HDU 1166 敌兵布阵

裸线段树题目，关于线段树的知识可以先看基本的教材，几乎任一本数据结构里都有的。先贴一下，动态申请内存的线段树，不过这种方法容易MLE include <cs

素颜马尾好姑娘i/ 2022年08月13日 11:37/ 0 赞/ 133 阅读

相关敌兵布阵

线段树: <pre name="code" class="cpp">include <stdio.h> include <string.h>

电玩女神/ 2022年08月03日 05:08/ 0 赞/ 142 阅读

相关敌兵布阵

Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地

左手的ㄟ右手/ 2022年08月02日 06:40/ 0 赞/ 143 阅读

相关 hdu 1166 敌兵布阵(树状数组)

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

雨点打透心脏的1/2处/ 2022年07月16日 13:18/ 0 赞/ 122 阅读

相关敌兵布阵 HDU - 1166

敌兵布阵 HDU - 1166 -------------------- Problem C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他

港控/mmm°/ 2022年06月14日 10:41/ 0 赞/ 137 阅读

相关敌兵布阵

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

桃扇骨/ 2022年06月12日 01:39/ 0 赞/ 168 阅读

相关 hdu 1166 敌兵布阵线段树

Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营

r囧r小猫/ 2022年06月08日 08:12/ 0 赞/ 177 阅读

相关敌兵布阵-线段树

敌兵布阵 Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎

Bertha 。/ 2022年06月03日 04:41/ 0 赞/ 137 阅读

相关 hdu 敌兵布阵

敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

布满荆棘的人生/ 2022年05月31日 10:44/ 0 赞/ 130 阅读