POJ 3468 线段树区间修改查询(Java,c++实现)

POJ 3468 (Java,c++实现)

Java

import java.io.*;

import java.util.*;

public class Main {

	static int n, m;

	static final int N = 100005;

	static int ls[] = new int[N << 2];

	static int rs[] = new int[N << 2];

	static long M[] = new long[N << 2];

	static long tag[] = new long[N << 2];

	private static Scanner sc;

	static void build(int k, int l, int r) throws IOException {

		int mid = (l + r) >> 1;

		ls[k] = l;

		rs[k] = r;

		tag[k] = 0;

		M[k] = 0;

		if (l == r) {

			M[k] = sc.nextInt();

			return;

		}

		build(k << 1, l, mid);

		build(k << 1 | 1, mid + 1, r);

		M[k] = M[k << 1] + M[k << 1 | 1];

	}

	static void pushdown(int k) {

		if (tag[k] == 0 || ls[k] == rs[k])

			return;

		tag[k << 1] += tag[k];

		tag[k << 1 | 1] += tag[k];

		int rage = (rs[k] - ls[k] + 1);

		M[k << 1] += (rage - (rage >> 1)) * tag[k];

		M[k << 1 | 1] += (rage >> 1) * tag[k];

		tag[k] = 0;

	}

	static void add(int k, int x, int y, int v) {

		pushdown(k);

		int l = ls[k], r = rs[k], mid = (l + r) >> 1;

		if (x == l && y == r) {

			tag[k] += v;

			M[k] += (long) v * (r - l + 1);

			return;

		}

		if (x <= mid)

			add(k << 1, x, Math.min(y, mid), v);

		if (y > mid)

			add(k << 1 | 1, Math.max(x, mid + 1), y, v);

		M[k] = M[k << 1] + M[k << 1 | 1];

	}

	static long query(int k, int x, int y) {

		pushdown(k);

		int l = ls[k], r = rs[k], mid = (l + r) >> 1;

		long ans = 0;

		if (x == l && y == r)

			return M[k];

		if (x <= mid)

			ans += query(k << 1, x, Math.min(y, mid));

		if (y > mid)

			ans += query(k << 1 | 1, Math.max(x, mid + 1), y);

		return ans;

	}

	public static void main(String[] args) throws IOException {

		sc = new Scanner(new InputStreamReader(System.in));

		int l = 0, r = 0, v, n, m;

		n = sc.nextInt();

		m = sc.nextInt();

		build(1, 1, n);

		char op;

		String tmp;

		while (m-- != 0) {

			tmp = sc.next();

			op = tmp.charAt(0);

			if (op == 'Q') {

				l = sc.nextInt();

				r = sc.nextInt();

				System.out.println(query(1, l, r));

			} else {

				l = sc.nextInt();

				r = sc.nextInt();

				v = sc.nextInt();

				add(1, l, r, v);

			}

		}

	}

}

C++

#include<queue>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

int n,m;

int ls[400005],rs[400005];

ll M[400005],tag[400005];

void build(int k,int l,int r)

{

    int mid=(l+r)>>1;

    ls[k]=l;

    rs[k]=r;

    tag[k]=0;

    M[k]=0;

    if(l==r)

    {

        M[k]=read();

        return;

    }

    build(k<<1,l,mid);

    build(k<<1|1,mid+1,r);

    M[k]=M[k<<1]+M[k<<1|1];

}

void pushdown(int k)

{

    if(!tag[k]||ls[k]==rs[k]) return;

    tag[k<<1]+=tag[k];

    tag[k<<1|1]+=tag[k];

    int rage=(rs[k]-ls[k]+1);

    M[k<<1]+=(rage-(rage>>1))*tag[k];

    M[k<<1|1]+=(rage>>1)*tag[k];

    tag[k]=0;

}

void add(int k,int x,int y,int v)

{

    pushdown(k);

    int l=ls[k],r=rs[k],mid=(l+r)>>1;

    if(x==l&&y==r)

    {

        tag[k]+=v;

        M[k]+=(ll)v*(r-l+1);

        return;

    }

    if(x<=mid) add(k<<1,x,min(y,mid),v);

    if(y>mid) add(k<<1|1,max(x,mid+1),y,v);

    M[k]=M[k<<1]+M[k<<1|1];

}

ll query(int k,int x,int y)

{

    pushdown(k);

    int l=ls[k],r=rs[k],mid=(l+r)>>1;

    ll ans=0;

    if(x==l&&y==r) return M[k];

    if(x<=mid)ans+=query(k<<1,x,min(y,mid));

    if(y>mid)ans+=query(k<<1|1,max(x,mid+1),y);

    return ans;

}

int main()

{

    int l,r,v,n,m;

    n=read();

    m=read();

    build(1,1,n);

    char op[3];

    while(m--)

    {

       scanf("%s",&op);

       if(op[0]=='Q'){

           l=read();r=read();

           printf("%lld\n",query(1,l,r));

       }else{

           l=read();r=read();v=read();

           add(1,l,r,v);

       }

    }

    return 0;

}