セグメントツリー
7465 ワード
uva 11983-Weird Advertisement(スキャンライン)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define ll long long
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std ;
const int maxn = 611111 ;
ll sum[15][maxn<<2] ;
int cnt[maxn<<2] , f[maxn<<1] , n , k ;
struct Edge{
int l , r , h , id ;
bool operator < ( const Edge &p ) const{
return h < p.h ;
}
} edge[maxn<<1] ;
void build(int l,int r,int rt){
cnt[rt]=0;
sum[0][rt]=f[r+1]-f[l];
for(int i=1;i<=k;i++)sum[i][rt]=0;
if(l==r)return;
int m=(l+r)>>1;
build(lson);
build(rson);
}
void push_up(int l,int r,int rt)// ，
{
int i ;
for ( i = 0 ; i <= k ; i ++ ) sum[i][rt] = 0 ;
if ( cnt[rt] >= k ) sum[k][rt] = f[r+1] - f[l] ;
else if ( l == r ) sum[cnt[rt]][rt] = f[r+1] - f[l] ;
else{
for ( i = k - cnt[rt] ; i <= k ; i ++ ) sum[k][rt] += sum[i][rt<<1] + sum[i][rt<<1|1] ;
for ( i = cnt[rt] ; i < k ; i ++ ) sum[i][rt] = sum[i-cnt[rt]][rt<<1] + sum[i-cnt[rt]][rt<<1|1] ;
}
}
void update(int L,int R,int flag,int l,int r,int rt){
if(L<=l&&R>=r){
cnt[rt]+=flag;
push_up(l , r , rt);
return;
}
int m=(l+r)>>1;
if(L<=m)update(L,R,flag,lson);
if(R>m)update(L,R,flag,rson);
push_up(l,r,rt);
}
int main () {
int a , b , c , d , cas , i , j , ca = 0 ;
scanf ( "%d" , &cas ) ;
while ( cas -- ){
scanf ( "%d%d" , &n , &k ) ;
int tot = 0 ;
ll ans = 0 ;
for ( i = 1 ; i <= n ; i ++ ){
scanf ( "%d%d%d%d" , &a , &b , &c , &d ) ;
c ++ , d ++ ;
tot ++ ;
edge[tot].l = a , edge[tot].r = c , edge[tot].h = b , edge[tot].id = 1 ;
f[tot] = a ;
tot ++ ;
edge[tot].l = a , edge[tot].r = c , edge[tot].h = d , edge[tot].id = -1 ;
f[tot] = c ;
}
sort ( f + 1 , f + tot + 1 ) ;
sort ( edge + 1 , edge + tot + 1 ) ;
int T = unique ( f + 1 , f + tot + 1 ) - f - 1 ;
build ( 1 , T - 1 , 1 ) ;
for ( i = 1 ; i < tot ; i ++ ){
int l = lower_bound ( f + 1 , f + T + 1 , edge[i].l ) - f ;
int r = lower_bound ( f + 1 , f + T + 1 , edge[i].r ) - f - 1 ;
update ( l , r , edge[i].id , 1 , T - 1 , 1 ) ;
ans += sum[k][1] * (ll) ( edge[i+1].h - edge[i].h ) ;
}
printf ( "Case %d: %lld
" , ++ ca , ans ) ;
}
}1455 - Kingdom
題意:いくつかの分散した都市があり、いくつかの都市を建設しながらこれらの都市をつなぎ、同じ連通ブロックの都市では州と呼ばれている.2つの操作があり、(1)roadを1本建設し、都市a,bを接続する.(2)縦座標cの水平線がいくつかの州を通過することができ、これらの州を通過する都市は合計でいくらであるかを尋ねる.
問題の構想を解く:そして差集+線分の木、そして差集の中で保存するのは州の情報で、記録するのは州の根のノードがあって、州の縦座標の最大値と最小値、およびこの州のsize(つまりこの州はいくつかの都市を含んで、横座標は実は役に立たない).2本の線分の木を建てて、それぞれ[l,r]がどれだけの州があるか、[l,r]がどれだけの都市があるかを保存して、それでは質問する時単点の質問です(cはあなたにk*0.5であることを教えて、あなたはすべての数を2倍に拡大することができて、それではすべて整数です).road操作時に、この2つの都市が属する集合を見つけて、まずあなたの2つの都市が同じ集合にあるかどうかを見て、同じ集合にある場合は、何も操作しません.そうでなければ、この2つの集合縦座標の最値関係に基づいて区間更新を行う(これは分類して議論するが、都市の個数は少なくないが、州の個数は減少する可能性があるので、よく議論する).そして2つの都市を同じ集合にまとめます.
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std ;
const int maxn = 1000002 ;
int sum[2][maxn<<2] , add[2][maxn<<2] ;
struct FA{
int fa , u , d , size ;
} f[maxn] ;
int find ( int a ) { return f[a].fa = ( a == f[a].fa ? a : find ( f[a].fa ) ) ; }
int p[maxn] ;
void push_down ( int rt , int flag ){
if ( add[flag][rt] ){
add[flag][rt<<1] += add[flag][rt] , add[flag][rt<<1|1] += add[flag][rt] ;
sum[flag][rt<<1] += add[flag][rt] , sum[flag][rt<<1|1] += add[flag][rt] ;
add[flag][rt] = 0 ;
}
}
void update ( int a , int b , int flag , int c , int l , int r , int rt ) {
if ( a > b ) return ;
if ( a <= l && r <= b ){
// printf ( "sum[%d][%d]" ) ;
sum[flag][rt] += c ;
// printf ( "a = %d , b = %d , l = %d , r = %d , c = %d
" , a , b , l , r , c ) ;
add[flag][rt] += c ;
return ;
}
push_down ( rt , flag ) ;
int m = ( l + r ) >> 1 ;
if ( a <= m ) update ( a , b , flag , c , lson ) ;
if ( m < b ) update ( a , b , flag , c , rson ) ;
sum[flag][rt] = sum[flag][rt<<1|1] + sum[flag][rt<<1] ;
}
int query ( int a , int flag , int l , int r , int rt ){
if ( l == r ) return sum[flag][rt] ;
push_down ( rt , flag ) ;
int m = ( l + r ) >> 1 , ret = 0 ;
if ( a <= m ) ret = query ( a , flag , lson ) ;
else ret = query ( a , flag , rson ) ;
return ret ;
}
char s[111] ;
int main (){
int n , i , j , k , cas , a , b , m , l , r , x , y ;
double c ;
scanf ( "%d" , &cas ) ;
while ( cas -- ){
scanf ( "%d" , &n ) ;
for ( i = 0 ; i < n ; i ++ ) {
scanf ( "%d%d", &a , &b ) ;
f[i].u = f[i].d = p[i] = b * 2 ;
f[i].size = 1 , f[i].fa = i ;
update ( b , b , 0 , 1 , 0 , maxn - 111 , 1 ) ;
update ( b , b , 1 , 1 , 0 , maxn - 111 , 1 ) ;
}
memset ( sum , 0 , sizeof ( sum ) ) ;
memset ( add , 0 , sizeof ( add ) ) ;
scanf ( "%d" , &m ) ;
while ( m -- ){
scanf ( "%s" , s ) ;
if ( s[0] == 'l' ){
scanf ( "%lf" , &c ) ;
c *= 2 ;
printf ( "%d %d
" , query ( c , 1 , 0 , maxn - 111 , 1 ) , query ( c , 0 , 0 , maxn - 111 , 1 ) ) ;
}
else{
scanf ( "%d%d" , &l , &r ) ;
x = find ( l ) , y = find ( r ) ;
if ( x == y ) continue ;
int u1 = f[x].u , u2 = f[y].u , d1 = f[x].d , d2 = f[y].d ;
// printf ( "%d %d %d %d %d %d
" , x , y , u1 , u2 , d1 , d2 ) ;
if ( d1 > u2 ) {
update ( u2 + 1 , u1 , 0 , f[y].size , 0 , maxn - 111 , 1 ) ;
update ( d2 , d1 - 1 , 0 , f[x].size, 0 , maxn - 111 , 1 ) ;
if ( d1 > u2 + 1 ) update ( u2 + 1 , d1 - 1 , 1 , 1 , 0 , maxn - 111 , 1 ) ;
}
else if ( d2 > u1 ){
update ( u1 + 1 , u2 , 0 , f[x].size , 0 , maxn - 111 , 1 ) ;
update ( d1 , d2 - 1 , 0 , f[y].size, 0 , maxn - 111 , 1 ) ;
if ( d2 > u1 + 1 ) update ( u1 + 1 , d2 - 1 , 1 , 1 , 0 , maxn - 111 , 1 ) ;
}
else if ( u2 >= d1 && u2 <= u1 ) {
update ( u2 + 1 , u1 , 0 , f[y].size , 0 , maxn - 111 , 1 ) ;
if ( d2 < d1 ) update ( d2 , d1 - 1 , 0 , f[x].size, 0 , maxn - 111 , 1 ) ;
else update ( d1 , d2 - 1 , 0 , f[y].size , 0 , maxn - 111 , 1 ) ;
// puts ( "fuck" ) ;
update ( max ( d1 , d2 ) , u2 , 1 , -1 , 0 , maxn - 111 , 1 ) ;
}
else {
update ( u1 + 1 , u2 , 0 , f[x].size , 0 , maxn - 111 , 1 ) ;
if ( d1 < d2 ) update ( d1 , d2 - 1 , 0 , f[y].size, 0 , maxn - 111 , 1 ) ;
else update ( d2 , d1 - 1 , 0 , f[x].size , 0 , maxn - 111 , 1 ) ;
update ( max ( d1 , d2 ) , u1 , 1 , -1 , 0 , maxn - 111 , 1 ) ;
}
f[y].u = max ( f[y].u , f[x].u ) ;
f[y].d = min ( f[y].d , f[x].d ) ;
f[x].fa = y ;
f[y].size += f[x].size ;
// printf ( "%d %d
" , query ( 9 , 1 , 0 , maxn - 111 , 1 ) , query ( 9 , 0 , 0 , maxn - 111 , 1 ) ) ;
}
}
}
return 0 ;
}
/*
3
10
1 7
5 7
8 6
3 5
5 5
2 3
10 3
7 2
4 1
11 1
11
road 0 1
road 3 5
road 4 2
road 3 8
line 4.5
*/