精华内容
下载资源
问答
  • 区间更新点查询 卡内存卡的比较死...1024*1024*4/1024恰好是规定的内存限制 看discuss说把原本开4倍的改成2倍,就过了 #include #include #include #include #include #include #include #include...

    Mobile phones

    Time Limit: 5000MS   Memory Limit: 65536K
    Total Submissions: 21877   Accepted: 10176

    Description

    Suppose that the fourth generation mobile phone base stations in the Tampere area operate as follows. The area is divided into squares. The squares form an S * S matrix with the rows and columns numbered from 0 to S-1. Each square contains a base station. The number of active mobile phones inside a square can change because a phone is moved from a square to another or a phone is switched on or off. At times, each base station reports the change in the number of active phones to the main base station along with the row and the column of the matrix. 

    Write a program, which receives these reports and answers queries about the current total number of active mobile phones in any rectangle-shaped area. 

    Input

    The input is read from standard input as integers and the answers to the queries are written to standard output as integers. The input is encoded as follows. Each input comes on a separate line, and consists of one instruction integer and a number of parameter integers according to the following table. 


    The values will always be in range, so there is no need to check them. In particular, if A is negative, it can be assumed that it will not reduce the square value below zero. The indexing starts at 0, e.g. for a table of size 4 * 4, we have 0 <= X <= 3 and 0 <= Y <= 3. 

    Table size: 1 * 1 <= S * S <= 1024 * 1024 
    Cell value V at any time: 0 <= V <= 32767 
    Update amount: -32768 <= A <= 32767 
    No of instructions in input: 3 <= U <= 60002 
    Maximum number of phones in the whole table: M= 2^30 

    Output

    Your program should not answer anything to lines with an instruction other than 2. If the instruction is 2, then your program is expected to answer the query by writing the answer as a single line containing a single integer to standard output.

    Sample Input

    0 4
    1 1 2 3
    2 0 0 2 2 
    1 1 1 2
    1 1 2 -1
    2 1 1 2 3 
    3
    

    Sample Output

    3
    4

    区间更新点查询

    卡内存卡的比较死...1024*1024*4/1024恰好是规定的内存限制

    看discuss说把原本开4倍的改成2倍,就过了

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <stack>
    #include <map>
    #include <set>
    #include <cmath>
    #include <vector>
    #include <bitset>
    #define max_ 1024
    #define inf 0x3f3f3f3f
    #define ll long long
    #define les 1e-8
    #define mod 364875103
    using namespace std;
    int tree[max_*2][max_*2];
    int n;
    void upda(int i,int x,int nl,int nr,int v,int id)
    {
        if(nl==nr)
        {
            tree[id][i]=max(0,tree[id][i]+v);
            return;
        }
        int mid=(nl+nr)>>1;
        if(x<=mid)
        upda(i<<1,x,nl,mid,v,id);
        else
        upda(i<<1|1,x,mid+1,nr,v,id);
        tree[id][i]=tree[id][i<<1]+tree[id][i<<1|1];
    }
    void up(int i,int x,int nl,int nr,int id)
    {
        tree[id][i]=tree[id<<1][i]+tree[id<<1|1][i];
        if(nl==nr)
        return;
        int mid=(nl+nr)>>1;
        if(x<=mid)
        up(i<<1,x,nl,mid,id);
        else
        up(i<<1|1,x,mid+1,nr,id);
    }
    void updata(int i,int x,int y,int nl,int nr,int v)
    {
        if(nl==nr)
        {
            upda(1,y,1,n,v,i);
            return;
        }
        int mid=(nl+nr)>>1;
        if(x<=mid)
        updata(i<<1,x,y,nl,mid,v);
        else
        updata(i<<1|1,x,y,mid+1,nr,v);
        up(1,y,1,n,i);
    }
    int que(int i,int l,int r,int nl,int nr,int id)
    {
        if(l==nl&&r==nr)
        {
            return tree[id][i];
        }
        int mid=(nl+nr)>>1;
        if(r<=mid)
        return que(i<<1,l,r,nl,mid,id);
        else if(l>mid)
        return que(i<<1|1,l,r,mid+1,nr,id);
        else
        return que(i<<1,l,mid,nl,mid,id)+que(i<<1|1,mid+1,r,mid+1,nr,id);
    }
    int query(int i,int l,int r,int nl,int nr,int dl,int dr)
    {
        if(l==nl&&r==nr)
        {
            return que(1,dl,dr,1,n,i);
        }
        int mid=(nl+nr)>>1;
        if(r<=mid)
        return query(i<<1,l,r,nl,mid,dl,dr);
        else if(l>mid)
        return query(i<<1|1,l,r,mid+1,nr,dl,dr);
        else
        return query(i<<1,l,mid,nl,mid,dl,dr)+query(i<<1|1,mid+1,r,mid+1,nr,dl,dr);
    }
    int main(int argc, char const *argv[]) {
        int m;
        while(scanf("%d",&m)!=EOF)
        {
            if(m==3)
            break;
            if(m==0)
            {
                scanf("%d",&n);
                memset(tree,0,sizeof tree);
            }
            else if(m==1)
            {
                int x,y,v;
                scanf("%d%d%d",&x,&y,&v);
                x++;
                y++;
                updata(1,x,y,1,n,v);
            }
            else if(m==2)
            {
                int x1,x2,y1,y2;
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                x1++;y1++;
                x2++;y2++;
                printf("%d\n",query(1,x1,x2,1,n,y1,y2));
            }
        }
        return 0;
    }

     

    展开全文
  • 二维线段树注意以下几个方面: X树更新时时要到底到叶节点(因为X树不能lazy),但查询时不用查到叶节点(= =因此tle了若干次)。 y树可以lazy,方法和普通线段树一样。 二维线段树的内存占用= = mid取得是...

    每个输入文件有多行。
    第一行,一个数n,表示鼹鼠的范围。
    以后每一行开头都有一个数m,表示不同的操作:
    m=1,那么后面跟着3个数x,y,k(0<=x,y<n),表示在点(x,y)处新出现了k只鼹鼠;
    m=2,那么后面跟着4个数x1,y1,x2,y2(0<=x1<=x2<n,0<=y1<=y2<n),表示询问矩形(x1,y1)-(x2,y2)内的鼹鼠数量;
    m=3,表示老师来了,不能玩了。保证这个数会在输入的最后一行。
    询问数不会超过10000,鼹鼠数不会超过maxlongint。

    n<=1024


     

    测试数据 #1: Accepted, time=0ms, mem=98806KB, score=10
    测试数据 #2: Accepted, time=124ms, mem=98806KB, score=10
    测试数据 #3: Accepted, time=15ms, mem=98806KB, score=10
    测试数据 #4: Accepted, time=15ms, mem=98806KB, score=10
    测试数据 #5: Accepted, time=109ms, mem=98806KB, score=10
    测试数据 #6: Accepted, time=0ms, mem=98806KB, score=10
    测试数据 #7: Accepted, time=62ms, mem=98806KB, score=10
    测试数据 #8: Accepted, time=31ms, mem=98806KB, score=10
    测试数据 #9: Accepted, time=15ms, mem=98802KB, score=10
    测试数据 #10: Accepted, time=140ms, mem=98806KB, score=10
    Time = 511ms Mem = 98806KB Score= 100


     

    这道题虽然是单点,但我写的是区间。(其实用树状数组做更快……只是用来试模板= =)

    二维线段树注意以下几个方面:

    • X树更新时时要到底到叶节点(因为X树不能lazy),但查询时不用查到叶节点(= =因此tle了若干次)。
    • y树可以lazy,方法和普通线段树一样。
    • 二维线段树的内存占用= =
    • mid取得是xl xr,而不是要查询的区间x1、x2

     

    Code

    program segtree2D;
    
    //Accepted
    
    type
     rec=record
       xl,xr,yl,yr:integer;
       add,sum:longint;
     end;
    
    Var
     f:array[0..3100,0..3100] of rec;
     n,m,i,j,x,y,k,x1,x2,y1,y2,op,top:longint;
    
    Function mmin(a,b:longint):longint;inline;begin if a<b then exit(a);exit(b); end;
    Function mmax(a,b:longint):longint;inline;begin if a>b then exit(a);exit(b); end;
    
    Procedure buildY(p,q:longint);
    var
     mid:longint;
      begin
      if q>top then top:=q;
      if f[p,q].yl=f[p,q].yr then exit;
      mid:=(f[p,q].yl+f[p,q].yr) div 2;
      with f[p,q*2] do
        begin
        xl:=f[p,q].xl;
        xr:=f[p,q].xr;
        yl:=f[p,q].yl;
        yr:=mid;
      end;
      buildy(p,q*2);
      with f[p,q*2+1] do
        begin
        xl:=f[p,q].xl;
        xr:=f[p,q].xr;
        yl:=mid+1;
        yr:=f[p,q].yr;
      end;
      buildY(p,q*2+1);
    end;
    
    Procedure buildx(P:longint);
    var
     mid:longint;
      begin
      f[p,1].yl:=0;f[p,1].yr:=n-1;
      buildy(p,1);
      if f[p,1].xl=f[p,1].xr then exit;
      mid:=(f[p,1].xl+f[p,1].xr) div 2;
      with f[p*2,1] do
        begin
        xl:=f[p,1].xl;
        xr:=mid;
      end;
      buildx(p*2);
      with f[p*2+1,1] do
        begin
        xl:=mid+1;
        xr:=f[p,1].xr;
      end;
      buildx(p*2+1);
    end;
    
    Procedure pushdown(p,q:longint);
      begin
      if p>top then exit;
      //writeln('push down ',p,' ',q,' #:',f[p,q].add);
      if q*2<=top then begin
      inc(f[p,q*2].sum,(f[p,q*2].yr-f[p,q*2].yl+1)*f[p,q].add);
      inc(f[p,q*2].add,f[p,q].add);   end;
      if q*2+1<=top then begin
      inc(f[p,q*2+1].sum,(f[p,q*2+1].yr-f[p,q*2+1].yl+1)*f[p,q].add);
      inc(f[p,q*2+1].add,f[p,q].add);     end;
      f[p,q].add:=0;
    end;
    
    Procedure addy(p,q,x1,x2,y1,y2,k:longint);
    var
     mid:longint;
      begin
      pushdown(p,q);
      with f[p,q] do
        begin
        if (yl=y1) and (yr=y2) then
          begin
          inc(sum,(yr-yl+1)*(x2-x1+1)*k);
          inc(add,k*(x2-x1+1));
          exit;
        end;
        mid:=(yl+yr) shr 1;
        if y1<=mid then addy(p,q*2,x1,x2,y1,mmin(y2,mid),k);
        if y2>mid then addy(p,q*2+1,x1,x2,mmax(y1,mid+1),y2,k);
        f[p,q].sum:=f[p,q*2].sum+f[p,q*2+1].sum;
      end;
    
    end;
    
    Procedure Addx(P,x1,y1,x2,y2,k:longint);
    var
     mid:longint;
      begin
      Addy(p,1,x1,x2,y1,y2,k);
      if (f[p,1].xr=f[p,1].xl) then exit;
      with f[p,1] do mid:=(xl+xr) div 2;
      if x1<=mid then Addx(p*2,x1,y1,mmin(x2,mid),y2,k);
      if x2>mid then Addx(p*2+1,mmax(mid+1,x1),y1,x2,y2,k);
    end;
    
    Function getsumy(p,q,x1,x2,y1,y2:longint):longint;
    var
     mid:longint;
      begin
      pushdown(p,q);  getsumy:=0;
      with f[p,q] do
        if (yl=y1) and (yr=y2) then
          begin
          //writeln('straight got!',yl,' ',yr,' ',f[p,q].sum);
          exit(f[p,q].sum)
        end
        else
          begin
          mid:=(yl+yr) shr 1;
          if y1<=mid then inc(getsumy,getsumy(p,q*2,x1,x2,y1,mmin(y2,mid)));
          if y2>mid then inc(getsumy,getsumy(p,q*2+1,x1,x2,mmax(y1,mid+1),y2));
        end;
      //writeln('getsumY',p,' ',x1,',',y1,' | ',x2,',',y2,' =',getsumy);
    end;
    
    Function getsumX(p,x1,y1,x2,y2:longint):longint;
    var
     mid:longint;
      begin
      getsumx:=0;
      with f[p,1] do
        if (xl=x1) and (xr=x2) then
          inc(getsumx,getsumy(p,1,x1,x2,y1,y2))
        else
          begin
          mid:=(xl+xr) shr 1;
          if x1<=mid then inc(getsumx,getsumx(p*2,x1,y1,mmin(x2,mid),y2));
          if x2>mid then inc(getsumx,getsumx(p*2+1,mmax(mid+1,x1),y1,x2,y2));
        end;
      //writeln('getsumX',p,' ',x1,',',y1,' | ',x2,',',y2,' =',getsumx);
    end;
    
    Procedure init(N:longint);
      begin
      with f[1,1] do
        begin
        xl:=0;
        xr:=n-1;
      end;
      Buildx(1);
    end;
    
      begin
      readln(n);
      init(n);
      top:=0;
      while true do
        begin
        read(op);
        case op of
          1:
            begin
            readln(x,y,k);
            AddX(1,x,y,x,y,k);
          end;
          2:
            begin
            readln(x1,y1,x2,y2);
            writeln(getsumX(1,x1,y1,x2,y2));
          end;
          3:
            halt;
        end;
     end;
    end.
    

     

     

    转载于:https://www.cnblogs.com/htfy/archive/2013/05/12/3073793.html

    展开全文
  • 传送门:UVA 11992题解 ... 线段树区间合并, 两个lazy有主次之分(set比add优先) pushDown()和pushUp(); /* adrui's submission Language : C++ Result : Accepted Love : ll Favorite : Dragon Balls Sta

    传送门:UVA 11992

    题解

    最多有20行, 可以建20棵线段树, 然后更新查询时按维数维护
    线段树区间合并, 两个lazy有主次之分(set比add优先)
    pushDown()和pushUp();

    /*
    adrui's submission
    Language : C++
    Result : Accepted
    Love : ll
    Favorite : Dragon Balls
    
    
    Standing in the Hall of Fame
    */
    
    
    #include<cstdio>
    #include<cstring>
    #include<queue>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    
    #define debug 0
    #define inf 0x7f7f7f7f
    #define mid ((l + r) >> 1)
    #define ls rt << 1, l, mid
    #define rs rt << 1|1, mid + 1, r
    #define M(a, b) memset(a, b, sizeof(a))
    
    int row, col, q;
    
    const int maxn(1e6 + 5);
    
    struct{
        int mx, mn, sum, addLayz, setLazy;
    }node[21][maxn << 2];
    
    void pushUp(int i, int rt) {
        node[i][rt].sum = node[i][rt << 1].sum + node[i][rt << 1 | 1].sum;
        node[i][rt].mx = max(node[i][rt << 1].mx, node[i][rt << 1 | 1].mx);
        node[i][rt].mn = min(node[i][rt << 1].mn, node[i][rt << 1 | 1].mn);
    }
    
    void build(int i, int rt, int l, int r) {
        node[i][rt].setLazy = -1;
        if (l == r) {
            return;
        }
    
        build(i, ls);
        build(i, rs);
        //pushUp(i, rt);
    }
    
    void pushDown(int i, int rt, int m) {
        if (node[i][rt].setLazy != -1) {
            node[i][rt << 1].sum = (m - (m >> 1)) * node[i][rt].setLazy;
            node[i][rt << 1 | 1].sum = (m >> 1) * node[i][rt].setLazy;
    
            node[i][rt << 1].mx = node[i][rt].setLazy;
            node[i][rt << 1 | 1].mx = node[i][rt].setLazy;
            node[i][rt << 1].mn = node[i][rt].setLazy;
            node[i][rt << 1 | 1].mn = node[i][rt].setLazy;
    
            node[i][rt << 1].addLayz = node[i][rt << 1 | 1].addLayz = 0;//set优先, 孩子节点的addLazy设为0
            node[i][rt << 1].setLazy = node[i][rt].setLazy;
            node[i][rt << 1 | 1].setLazy = node[i][rt].setLazy;
    
            node[i][rt].setLazy = -1;
        }
    
        if (node[i][rt].addLayz != 0) {
            node[i][rt << 1].sum += (m - (m >> 1)) * node[i][rt].addLayz;
            node[i][rt << 1 | 1].sum += (m >> 1) * node[i][rt].addLayz;
    
            node[i][rt << 1].mx += node[i][rt].addLayz;
            node[i][rt << 1 | 1].mx += node[i][rt].addLayz;
            node[i][rt << 1].mn += node[i][rt].addLayz;
            node[i][rt << 1 | 1].mn += node[i][rt].addLayz;
    
            node[i][rt << 1].addLayz += node[i][rt].addLayz;
            node[i][rt << 1 | 1].addLayz += node[i][rt].addLayz;
    
            node[i][rt].addLayz = 0;
        }
    
    
    }
    
    void addVal(int i, int rt, int l, int r, int ul, int ur, int add) {     //add
        if (ul <= l && ur >= r) {
            node[i][rt].sum += (r - l + 1) * add;
            node[i][rt].mx += add;
            node[i][rt].mn += add;
            //if (node[i][rt].setLazy != -1)  node[i][rt].setLazy += add;
            node[i][rt].addLayz += add;
            return;
        }
    
        pushDown(i, rt, r - l + 1);
    
        if(ul <= mid)   addVal(i, ls, ul, ur, add);
        if (ur > mid)   addVal(i, rs, ul, ur, add);
    
        pushUp(i, rt);
    }
    
    void setVal(int i, int rt, int l, int r, int ul, int ur, int v) {       //set
        if (ul <= l && ur >= r) {
            node[i][rt].sum = (r - l + 1) * v;
            node[i][rt].mx = v;
            node[i][rt].mn = v;
            node[i][rt].setLazy = v;
            node[i][rt].addLayz = 0;//优先
            return;
        }
    
        pushDown(i, rt, r - l + 1);
    
        if (ul <= mid)  setVal(i, ls, ul, ur, v);
        if (ur > mid)   setVal(i, rs, ul, ur, v);
    
        pushUp(i, rt);
    }
    
    void query(int i, int rt, int l, int r, int ql, int qr, int &sum, int &mn, int &mx) {//query
        if (ql <= l && qr >= r) {
            sum += node[i][rt].sum;
            mx = max(mx, node[i][rt].mx);
            mn = min(mn, node[i][rt].mn);
            return;
        }
    
        pushDown(i, rt, r - l + 1);
    
        if (ql <= mid) query(i, ls, ql, qr, sum, mn, mx);
        if (qr > mid)  query(i, rs, ql, qr, sum, mn, mx);
        pushUp(i, rt);
    }
    int main() {
    #if debug
        freopen("in.txt", "r", stdin);
    #endif //debug
    
        cin.tie(0);
        cin.sync_with_stdio(false);
    
        int k, x1, y1, x2, y2, v;
        while (cin >> row >> col >> q) {
    
            M(node, 0);
            for (int i = 1; i <= row; i++)                          //建树
                build(i, 1, 1, col);
    
            while (q--) {
                cin >> k;
    
                if (k == 3) {
                    cin >> x1 >> y1 >> x2 >> y2;
                    int sum = 0;
                    int mn = inf, mx = -inf;
    
                    for (int i = x1; i <= x2; i++) {
                        query(i, 1, 1, col, y1, y2, sum, mn, mx);
                    }
    
                    cout << sum << " " << mn << " " << mx << endl;
                }
                else {
                    cin >> x1 >> y1 >> x2 >> y2 >> v;
                    if (k == 1) {
                        for (int i = x1; i <= x2; i++)
                            addVal(i, 1, 1, col, y1, y2, v);
                    }
                    else {
                        for (int i = x1; i <= x2; i++)
                            setVal(i, 1, 1, col, y1, y2, v);
                    }
                }
            }
        }
        return 0;
    }
    展开全文
  • //FAFU 1100 线段树 二维线段树 单点更新 区间求和 /* 题意: 一个矩阵,初始化为0,两种操作: 1、将某点增加val 2、查询一个子矩阵的和 思路: 二维线段树,单点更新区间求和,记得pushup. */ #include #...
    //FAFU 1100 线段树 二维线段树 单点更新 区间求和
    /*
    题意:
    一个矩阵,初始化为0,两种操作:
    1、将某点增加val
    2、查询一个子矩阵的和
    
    思路:
    二维线段树,单点更新,区间求和,记得pushup.
    */
    
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    #define N 1050
    #define lson rt<<1,l,mid
    #define rson rt<<1|1,mid+1,r
    
    int sum[N*3][N*3];
    int n;
    
    void SubBuild(int rt,int l,int r,int t){
    	sum[t][rt] = 0;
    	if(l!=r){
    		int mid = (l + r) >> 1;
    		SubBuild(lson,t);
    		SubBuild(rson,t);
    	}
    }
    
    void Build(int rt,int l,int r){
    	SubBuild(1,1,n,rt);
    	if(l!=r){
    		int mid = (l + r) >> 1;
    		Build(lson);
    		Build(rson);
    	}
    }
    
    void SubUpdate(int rt,int l,int r,int y,int val,int t){
    	if(l == r)
    		sum[t][rt] += val;
    	else{
    		int mid = (l + r) >> 1;
    		if(y <= mid) SubUpdate(lson,y,val,t);
    		else		 SubUpdate(rson,y,val,t);
    		sum[t][rt] = sum[t][rt<<1] + sum[t][rt<<1|1];
    	}
    }
    
    void Update(int rt,int l,int r,int x,int y,int val){
    	SubUpdate(1,1,n,y,val,rt);
    	if(l!=r){
    		int mid = (l + r) >> 1;
    		if(x <= mid) Update(lson,x,y,val);
    		else		 Update(rson,x,y,val);
    	}
    }
    
    __int64 SubQuery(int rt,int l,int r,int LY,int RY,int t){
    	if(LY <= l && RY >= r)
    		return sum[t][rt];
    	int mid = (l + r) >> 1;
    	__int64 ans = 0;
    	if(LY <= mid) ans += SubQuery(lson,LY,RY,t);
    	if(RY > mid ) ans += SubQuery(rson,LY,RY,t);
    	return ans;
    }
    
    __int64 Query(int rt,int l,int r,int LX,int RX,int LY,int RY){
    	if(LX <= l && RX >= r){
    		return SubQuery(1,1,n,LY,RY,rt);
    	}
    	int mid = (l + r) >> 1;
    	__int64 ans = 0;
    	if(LX <= mid) ans += Query(lson,LX,RX,LY,RY);
    	if(RX > mid ) ans += Query(rson,LX,RX,LY,RY);
    	return ans;
    }
    
    int main(){
    	int op;
    	int a,b,c,d;
    	while(scanf("%d %d",&op,&n)!=EOF){
    		++n;
    		Build(1,1,n);
    		while(scanf("%d",&op)){
    			if(op == 3)
    				break;
    			if(op == 1){
    				scanf("%d %d %d",&a,&b,&c);
    				++a,++b;
    				Update(1,1,n,a,b,c);
    			}
    			else{
    				scanf("%d %d %d %d",&a,&b,&c,&d);
    				++a,++b,++c,++d;
    				printf("%I64d\n",Query(1,1,n,a,c,b,d));
    			}
    		}
    	}
    	return 0;
    }

    展开全文
  • 区间更新点查询 身高范围是100-200,减99变成1-101 活力范围是0.0-100.0,乘10加1变成1-1001 比较坑的是H1 H2 A1 A2的大小关系是不确定的 再有就是查询不到时输出的是-1不是-1.0 =.= #include #...
  • //POJ 1195 Mobile phones 线段树 二维线段树 单点更新 区间求和 /* 题意: 一个矩阵,初始化为0,两种操作: 1、将某点增加val 2、查询一个子矩阵的和 思路: 二维线段树,单点更新区间求和,记得pushup. */ #...
  • 题意: 中文题 解题思路: 利用二维线段树的点更新即可 注意: 二维线段树的在点更新时,需先更新局部的子区间,然后更新全局区间
  • 之前只做过二维的树状数组,二维线段树真不会啊,我直接搜了个博客,看懂了以后直接复制了他的博客,因为原文注释比较少,所以我就加上了我的注释,也是我的理解。。。真想知道世界上第一个想出二维线段树的人是这么...
  • 题意: 算一个子矩形内的最大和最小的平均值,并将该平均值更新到该子矩形的中心(该矩形的边为奇数) 解题思路: ...利用二维线段树的点更新和...二维线段树的在点更新时,需先更新局部的子区间,然后更新全局区间
  • 思路:就是构造二维线段树,然后就是单点跟新,区间最值了。 /* 题意:给你一个矩阵,随后m行,x,y,l,从x行y列,扩大l/2个格子,不能出界,表示要查询的矩阵大小, 查询最小值与最大值,然后
  • 如果写二维线段树区间RMQ,不能单点更新的话,那么和咸鱼有什么区别。 所以弄了一个下午,终于把更新弄出来了。。。 这个是这样的,既然是单点更新,一定会更新到最底层,因此先更新到第一维的最底层,在到第二维...
  • 更新区间查询 #include #include #include #include #include #include #include #include #include #include #include #define max_ 110 #define inf 0x3f3f3f3f #define ll long long #define ...
  • 二维线段树

    千次阅读 2017-04-13 16:24:44
    最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域最值,更加高效的方法是二维RMQ,但是二维RMQ不支持动态更新,所以二维...
  • 二维线段树区间更新和单点查询,由于二维线段树不能传递标记,所以区间更新和一维不太一样,需要用到被更新的值以及更新操作的一些性质,还有要注意对query的影响。 这里操作是翻转,而且是单点查询,所以就直接在...
  • 这题我们并不方便直接将每次操作更新到叶子节点,也不需要打lazy标记,只需要在查询的时候将从根节点到我们目标节点一路上被更新的次数相加%2 #include using namespace std; const int N = 1e3 + 10; ...
  • 二维线段树的维护用于pushdown操作不能实现(你会发现不断递归才能找到正确答案) 而对于pushup操作,似乎也不方便(待会可以试试) 这时引入一个标记永久化的概念, 我们在维护线段树时会使用一个max数组维护...
  • 二维线段树专题

    2018-10-06 21:35:42
    最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域最值,更加高效的方法是二维RMQ,但是二维RMQ不支持动态更新,所以二维...
  • 二维线段树详解

    2019-08-17 00:06:54
    最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域最值,更加高效的方法是二维RMQ,但是二维RMQ不支持动态更新,所以二维...
  • //POJ 2029 Get Many Persimmon Trees 二维线段树 单点更新 区间求和 /* 题意:一个0,1矩阵,在其n*m的子矩阵中找出含有1最多的,输出最多的数量 思路:二维线段树 */ #include #include #include #define N 105...
  • 分析:二维线段树裸题,留作板子。二维线段树就是在一棵线段树的每一个节点,都保存着另一棵线段树的根节点编号。注意更新操作,稍微有点复杂,给个图解。可以结合代码理解,代码在关键地方写了注释。(感谢xbb的...
  • 最经典的就是求区间最值(或区间和),推广到二维,求得就是矩形区域最值(或矩形区域和),对于矩形区域和,二维树状数组更加高效,而矩形区域最值,更加高效的方法是二维RMQ,但是二维RMQ不支持动态更新,所以二维...
  • 二维线段树的板子题,查询时修改X1,Y1,X2,Y2,然后直接query_x,查询后minx和maxx均会被修改。更新也是如此,先修改X1,Y1,X2,Y2,然后把val改成需要修改的值,直接update。 就是这么无脑地用板子。。 ...
  • 题意: 有一个n*n的矩阵,初始化全部为0。有2中操作; 1、给一个子矩阵,将这个子矩阵里面所有的0变成1,1变成0;...思路: 二维线段树,一维线段树的成段更新需要lazy。 引申到二维线段树应该需要一个lazy,一个...
  • 仅仅是这里是二维的树状数组,原理是一样的。 将其改变的话,能够如此,如果最開始[1....x2][1....y2]为偶数的话(这里就是看成是前辍和) 先将[1....x2][1....y2]添加1,变为奇数,然后将[1...x1 - 1][y2]添加1...

空空如也

空空如也

1 2 3 4 5 ... 10
收藏数 182
精华内容 72
关键字:

二维线段树区间更新