HDU 1754 I Hate It
点更新+段查询#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 200000+10;
int n,num[maxn],m;
struct node{
int lson,rson;
int mid(){
return lson+(rson-lson)/2;
}
int maxx;
}tree[maxn*3];
void pushup(int rt){
tree[rt].maxx = max(tree[rt<<1].maxx,tree[rt<<1|1].maxx);
}
void build(int l,int r,int root){
tree[root].lson = l;
tree[root].rson = r;
if(l==r) {
tree[root].maxx = num[l];
return;
}
int mid = tree[root].mid();
build(l,mid,root<<1);
build(mid+1,r,root<<1 | 1);
pushup(root);
}
void update(int pos,int val,int rt){
if(tree[rt].lson==tree[rt].rson){
tree[rt].maxx = val;
return;
}
int mid =tree[rt].mid();
if(pos <= mid) update(pos,val,rt<<1);
else update(pos,val,rt<<1|1);
pushup(rt);
}
int query(int L,int R,int root){
if(L<=tree[root].lson&&tree[root].rson<=R)
return tree[root].maxx;
int mid = tree[root].mid();
if(mid >= R) {
return query(L,R,root*2);
}
else if(mid < L){
return query(L,R,root*2+1);
}
else{
return max(query(L,R,root*2),query(L,R,root*2+1));
}
}
int main(){
while(cin >> n >> m){
for(int i = 1; i <= n; i++) scanf("%d",&num[i]);
build(1,n,1);
char op;
int a,b;
while(m--){
cin >> op;
if(op==‘Q‘){
scanf("%d%d",&a,&b);
cout << query(a,b,1)<<endl;
}else{
scanf("%d%d",&a,&b);
update(a,b,1);
}
}
}
return 0;
}
HDU 1698 Just a Hook
成段更新
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100000+10;
struct node{
int lson,rson;
int mid(){
return lson + (rson-lson)/2;
}
int sum,lazy;
}tree[maxn*4];
int n,m;
void pushup(int rt){
tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
}
void pushdown(int rt){
if(tree[rt].lazy > 0){
tree[rt<<1].lazy = tree[rt<<1|1].lazy = tree[rt].lazy;
tree[rt<<1].sum = (tree[rt<<1].rson-tree[rt<<1].lson+1)*tree[rt].lazy;
tree[rt<<1|1].sum = (tree[rt<<1|1].rson-tree[rt<<1|1].lson+1)*tree[rt].lazy;
tree[rt].lazy = 0;
}
}
void build(int l,int r,int rt){
tree[rt].lson = l;
tree[rt].rson = r;
tree[rt].lazy = 0;
if(l==r){
tree[rt].sum = 1;
return;
}
int mid = tree[rt].mid();
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
pushup(rt);
}
void update(int L,int R,int rt,int lazy){
if(L<=tree[rt].lson&&tree[rt].rson<=R){
tree[rt].lazy = lazy;
tree[rt].sum = lazy*(tree[rt].rson-tree[rt].lson+1);
return;
}
pushdown(rt);
int mid = tree[rt].mid();
if(L <= mid) update(L,R,rt<<1,lazy);
if(R > mid) update(L,R,rt<<1|1,lazy);
pushup(rt);
}
int main(){
int ncase,T=1;
cin >> ncase;
while(ncase--){
scanf("%d%d",&n,&m);
build(1,n,1);
while(m--){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
update(a,b,1,c);
}
printf("Case %d: The total value of the hook is %d.\n",T++,tree[1].sum);
}
return 0;
}
逆序数问题。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 5000+10;
int n,num[maxn],m;
struct node{
int lson,rson;
int mid(){
return lson + (rson-lson)/2;
}
int sum;
}tree[maxn*4];
void pushup(int rt){
tree[rt].sum = tree[rt<<1].sum+tree[rt<<1|1].sum;
}
void build(int l,int r,int rt){
tree[rt].lson = l;
tree[rt].rson = r;
tree[rt].sum = 0;
if(l==r) return;
int mid = tree[rt].mid();
build(l,mid,rt<<1);
build(mid+1,r,rt<<1 | 1);
}
void update(int pos,int rt){
if(tree[rt].lson==tree[rt].rson){
tree[rt].sum++;
return;
}
int mid = tree[rt].mid();
if(pos<=mid) update(pos,rt<<1);
else update(pos,rt<<1|1);
pushup(rt);
}
int query(int L,int R,int rt){
if(L<=tree[rt].lson&&tree[rt].rson<=R)
return tree[rt].sum;
int mid = tree[rt].mid();
int res = 0;
if(L <= mid) res += query(L,R,rt<<1);
if(R > mid) res += query(L,R,rt<<1|1);
return res;
}
int main(){
while(cin >> n){
build(0,n-1,1);
int res = 0;
for(int i = 0; i < n; i++){
scanf("%d",&num[i]);
res += query(num[i],n-1,1);
update(num[i],1);
}
int ans = res;
for(int i = 0; i < n; i++){
res += n-num[i]*2-1;
ans = min(ans,res);
}
cout<<ans<<endl;
}
return 0;
}
HDU1542 Atlantis
扫描线
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 100000+10;
struct line{
double x,bot,up;
int flag;
line(double x,double bot,double up,int flag):x(x),bot(bot),up(up),flag(flag){}
friend bool operator <(line a,line b){
return a.x < b.x;
}
};
vector<line> vl;
vector<double> vd;
int n;
struct node{
double lson,rson;
double x;
int cover;
int flag;
int mid(){
return lson + (rson-lson)/2;
}
}tree[maxn*4];
void build(int l,int r,int rt){
tree[rt].lson = vd[l];
tree[rt].x = -1;
tree[rt].rson = vd[r];
tree[rt].cover = 0;
tree[rt].flag = 0;
if(l+1==r){
tree[rt].flag = 1;
return;
}
int mid =(l+r)>>1;
build(l,mid,rt<<1);
build(mid,r,rt<<1|1);
}
double insert(double x,double bot,double top,int cnt,int rt){
if(tree[rt].lson >= top || tree[rt].rson <= bot) return 0;
if(tree[rt].flag){
if(tree[rt].cover>0){
double t = tree[rt].x,ans=0;
ans = (x-t)*(tree[rt].rson-tree[rt].lson);
tree[rt].x = x;
tree[rt].cover += cnt;
return ans;
}else{
tree[rt].x = x;
tree[rt].cover += cnt;
return 0;
}
}
return insert(x,bot,top,cnt,rt<<1)+insert(x,bot,top,cnt,rt<<1|1);
}
int main(){
int T=1;
while(cin >> n && n){
vl.clear();
vd.clear();
for(int i = 0; i < n; i++){
double x1,y1,x2,y2;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
vl.push_back(line(x1,y1,y2,1));
vl.push_back(line(x2,y1,y2,-1));
vd.push_back(y1);
vd.push_back(y2);
}
sort(vd.begin(),vd.end());
sort(vl.begin(),vl.end());
build(0,vl.size()-1,1);
double ans = 0;
for(int i = 0; i < vl.size(); i++){
ans += insert(vl[i].x,vl[i].bot,vl[i].up,vl[i].flag,1);
}
printf("Test case #%d\nTotal explored area: %.2lf\n",T++,ans);
cout<<endl;
}
return 0;
}
HDU 1264 Counting Squares
扫描线
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 100+10;
struct node{
int x,lson,rson;
int len,cover;
int mid(){
return lson + (rson-lson)/2;
}
}tree[maxn*6];
struct line{
int x,y1,y2;
int flag;
friend bool operator <(line a,line b){
return a.x < b.x;
}
line(int x,int y1,int y2,int flag):x(x),y1(y1),y2(y2),flag(flag){}
};
vector<line> vl;
void pushup(int rt){
if(tree[rt].cover){
tree[rt].len = tree[rt].rson+1-tree[rt].lson;
return;
}
tree[rt].len = tree[rt<<1].len + tree[rt<<1|1].len;
}
void build(int l,int r,int rt){
tree[rt].lson = l;
tree[rt].rson = r;
tree[rt].cover = 0;
tree[rt].len = 0;
if(l==r) return;
int mid = tree[rt].mid();
build(l,mid,rt<<1);
build(mid+1,r,rt<<1|1);
}
void update(int L,int R,int rt,int flag){
if(L <= tree[rt].lson && tree[rt].rson <= R){
tree[rt].cover += flag;
pushup(rt);
return;
}
int mid = tree[rt].mid();
if(L <= mid) update(L,R,rt<<1,flag);
if(R > mid) update(L,R,rt<<1|1,flag);
pushup(rt);
}
int main(){
int x1,y1,x2,y2;
int t=0;
while(1){
vl.clear();
while(~scanf("%d%d%d%d",&x1,&y1,&x2,&y2)){
if(x1==-1&&x2==-1&&y1==-1&&y2==-1){
break;
}
if(x1==-2&&y1==-2&&x2==-2&&y2==-2){
t = 1;
break;
}
if(x1 > x2) swap(x1,x2);
if(y1 > y2) swap(y1,y2);
vl.push_back(line(x1,y1,y2,1));
vl.push_back(line(x2,y1,y2,-1));
}
build(0,maxn,1);
sort(vl.begin(),vl.end());
int ans = 0;
for(int i = 0; i < vl.size()-1; i++){
int L = vl[i].y1;
int R = vl[i].y2-1;
update(L,R,1,vl[i].flag);
ans += (vl[i+1].x-vl[i].x)*tree[1].len;
}
cout<<ans<<endl;
if(t) break;
}
return 0;
}
原文：http://blog.csdn.net/mowayao/article/details/24979517