Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

论不会lowbit的任性~!

Posted by hjxcpg at 2015-12-02 17:04:40 on Problem 1195
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator