1176: [Balkan2007]Mokia

1176: [Balkan2007]Mokia

链接

分析

  三维偏序问题,CDQ分治论文题。

代码

 #include<bits/stdc++.h>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for (;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} int ans[],W;
struct Que{
int ty,x,y,w,id;
bool operator < (const Que &a) const {
return x == a.x ? ty < a.ty : x < a.x;
}
}A[*++],B[*++]; struct Bit{
int sum[];
void update(int p,int v) {
for (; p<=W; p+=p&(-p)) sum[p] += v;
}
int query(int p) {
int ans = ;
for (; p; p-=p&(-p)) ans += sum[p];
return ans;
}
void clear(int p) {
for (; p<=W&&sum[p]; p+=p&(-p)) sum[p] = ;
}
}bit; void CDQ(int L,int R) {
if (L == R) return ;
int M = (L + R) >> ;
CDQ(L,M);
CDQ(M+,R);
int i = L, j = M + ,k = L;
while (i <= M && j <= R) {
if (A[i] < A[j]) {
if (A[i].ty == ) bit.update(A[i].y,A[i].w);
B[k++] = A[i++];
}
else {
if (A[j].ty == ) ans[A[j].id] += A[j].w * bit.query(A[j].y);
B[k++] = A[j++];
}
}
while (i <= M) B[k++] = A[i++];
while (j <= R) {
ans[A[j].id] += A[j].w * bit.query(A[j].y);
B[k++] = A[j++];
}
for (int i=L; i<=R; ++i) {
bit.clear(A[i].y);
A[i] = B[i];
}
}
int main() { W = read();W = read(); // 把W在这里int了一下,然后。。。
int Index = ,QueIndex = ; while () {
int opt = read();
if (opt==) break;
if (opt==) {
int a = read(),b = read(),val = read();
A[++Index] = (Que){,a,b,val,};
}
else {
int a1 = read(),b1 = read(),a2 = read(),b2 = read();
A[++Index] = (Que){,a1-,b1-,,++QueIndex};
A[++Index] = (Que){,a1-,b2,-,QueIndex};
A[++Index] = (Que){,a2,b1-,-,QueIndex};
A[++Index] = (Que){,a2,b2,,QueIndex};
}
}
CDQ(,Index);
for (int i=; i<=QueIndex; ++i) printf("%d\n",ans[i]);
return ;
}
上一篇:原生php如何获取当前页面的url


下一篇:IM协议