| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
论不会lowbit的任性~!#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
using namespace std;
int i,s,p,f[2100][2100],q,qq,h,z,va,lj,yy,y2,x1,x2;
void cr(int x,int y,int xh)
{
if (z>=x && z<=y) f[q][xh]+=va;
else return;
if (x==y) return;
cr(x,(x+y)>>1,xh<<1); cr(((x+y)>>1)+1,y,(xh<<1)+1);
}
void cc(int x,int y,int xh)
{
if (h>=x && h<=y) { q=xh; cr(1,s,1); }
else return;
if (x==y) return;
cc(x,(x+y)>>1,xh<<1); cc(((x+y)>>1)+1,y,(xh<<1)+1);
}
void fi(int x,int y,int xh)
{
if (x>y2 || y<yy) return;
if (x>=yy && y<=y2) { lj+=f[qq][xh]; return; }
fi(x,(x+y)>>1,xh<<1); fi(((x+y)>>1)+1,y,(xh<<1)+1);
}
void qh(int x,int y,int xh)
{
if (y<x1 || x>x2) return;
if (x>=x1 && y<=x2) { qq=xh; fi(1,s,1); return; }
qh(x,(x+y)>>1,xh<<1); qh(((x+y)>>1)+1,y,(xh<<1)+1);
}
int main()
{
while (~scanf("%d",&p))
{
if (p==0) { memset(f,0,sizeof(f)); scanf("%d",&s); }
else
if (p==1)
{ scanf("%d%d%d",&h,&z,&va); h++; z++; cc(1,s,1); }
else
if (p==2)
{ scanf("%d%d%d%d",&x1,&yy,&x2,&y2); lj=0; x1++; x2++; yy++; y2++; qh(1,s,1); printf("%d\n",lj); }
else break;
}
}
人工线段树,就是这么吊
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator