[BZOJ] 2141 - Atlantis - 줄 서기 - 트 리 배열 역순 맞 추기 - 블록 구 구간 k 보다 작 음

2141: 줄 서기
Time Limit: 4 Sec  
Memory Limit: 259 MB
Submit: 2506  
Solved: 982
[ Submit][ Status][ Discuss]
Description
줄 지어 앉 아 과일 을 먹고, 생 과일 이 달 고, 모두들 하하 웃 었 다.너 하나, 나 하나, 큰 것 은 너 에 게 나 누 어 주 고 작은 것 은 나 에 게 남 겨 주 며 과일 을 먹고 노래 를 부 르 면 모두 즐 겁 고 화목 하 다.홍 성 유치원 어린이 들 은 과일 을 먹 으 려 고 길 게 줄 을 섰 다.하지만 어린이 들 의 키 가 다 르 기 때문에 줄 을 서 있 는 팀 의 높낮이 가 어 지 러 워 아름 답지 않다.i 번 째 어린이의 키 를 hi 로 설정 합 니 다. 우 리 는 하나의 서열 의 난잡 정 도 를 ihj 의 (i, j) 수량 을 만족 시 키 는 것 으로 정의 합 니 다.유치원 아 주머니 는 매번 두 명의 어린 이 를 뽑 아 그들의 위 치 를 교환 합 니 다. 매번 교환 한 후에 서열 의 난잡 한 정 도 를 계산 해 주세요.유치원 아 줌 마 의 통 계 를 편리 하 게 하기 위해 서 는 어떤 교환 작업 도 하지 않 았 을 때 도 이 서열 의 난잡 한 정 도 를 수출 해 야 한다.
Input
첫 번 째 행 위 는 정수 n 으로 어린이 수 를 나타 낸다.두 번 째 줄 은 n 개의 빈 칸 으로 구 분 된 정수 h1, h2,..., hn 을 포함 하여 초기 대기 열 중 소 친구 의 키 를 순서대로 표시 합 니 다.세 번 째 행 위 는 정수 m 로 교환 작업 의 횟수 를 나타 낸다.아래 m 줄 에는 두 개의 정수 ai 와 bi € 가 포함 되 어 있 으 며, 위 치 를 교환 하 는 ai 와 위치 bi 의 어린 이 를 나타 낸다.
Output
출력 파일 은 모두 m 줄 이 고 i 줄 의 정 수 는 교환 작업 i 가 끝 난 후에 서열 의 복잡 도 를 나타 낸다.
Sample Input
[샘플 입력] 3, 130, 150, 140, 2, 3, 1, 3.
Sample Output
1. 0. 3 [사례 설명] 어떠한 조작 도 하지 않 았 을 때 (2, 3) 조건 을 만족시킨다.조작 1 이 끝 난 후에 서열 은 130 140 150 이 고 ihj 를 만족 시 키 는 (i, j) 쌍 이 존재 하지 않 습 니 다.조작 2 가 끝 난 후 서열 은 150 140 130, (1, 2), (1, 3), (2, 3) 모두 3 쌍 이 조건 을 만족 시 키 는 (i, j) 이다.【 데이터 규모 와 약 정 】 100% 의 데이터 에 대해 1 ≤ m ≤ 2 * 103, 1 ≤ n ≤ 2 * 104, 1 ≤ hi ≤ 109, ai ≠ bi, 1 ≤ ai, bi ≤ n.
HINT
Source
제목 의 뜻 이 분명 하 다.
바로 1Y 혼 이 들 어가 서 흐뭇 해 요.
길이 n 의 수열  m 차 조작  매번 조작 할 때마다 두 개의 서로 다른 위치의 숫자 를 교환한다
매번 조작 후 역순 으로 맞 는 개 수 를 묻다
우선 선분 트 리 or 를 정렬 하거나 트 리 모양 배열 로 초기 역순 쌍 의 개 수 를 구 합 니 다.
그리고 매번 조작 을 봐 요.
왼쪽 에 있 는 그 위 치 를 l 로 설정 합 니 다.   오른쪽 에 있 는 그 위 치 는 r 입 니 다.
[l, r] 구간 만 이 전체 국면 에 영향 을 미 칠 수 있다.
[l, r] 구간 외 에 작 아야 할 것 은 작 아야 합 니까?   커 야 할 것 은 커 야 할 것 인가
구간  ma [l], ma [r] 보다 작은 것 이 몇 개 있 는 지 통계 해 야 합 니 다.  몇 개가 마 [l], 마 [r] 보다 큽 니까?
그리고 블록 으로 풀 어 볼 까 생각 중이 에 요.
구체 적 인 해법 은 여러 색 과 유사 하 다. http://blog.csdn.net/yiranluoshen/article/details/78224787
블록 마다 정렬 하기
매번 전체 블록 을 찾 을 때마다 직접 2 분 씩 찾 습 니 다.
복잡 도 는 O (log (sqrt (n))))
약간 짜증 나 는 게 교환 할 때 어떻게 업데이트 하 는 지.
나의 해법 은 원래 의 배열 에 대해 직접 교환 하 는 것 이다.
정렬 된 배열 에서 먼저 2 분 동안 원 데이터 의 위 치 를 찾 습 니 다.
업데이트
그리고 이동.
이렇게 업데이트 할 때마다 복잡 도 는 O (log (sqrt (n) + sqrt (n)) 입 니 다.
1Y 때 도 깜짝 놀 랐 어 요.
1300 ms 는 빠 른 편 이 아니에요.
600 ms 가 있 더 라 고요.
복잡 도 는 O (sqrt (n) logn 인 것 같 아 요.
블록 마다 트 리 배열 을 만 듭 니 다.
멍 하 다
다음 연구

#include 
#define pb push_back
using namespace std;

const int N = 20010;

int n, m;
int bits[N];
int ma[N];
int cp[N];///           
int block;
int num;
int bo[N];
int bl[N];
int br[N];
int ans;
int len;
vector id;

int getid(int x)
{
    return lower_bound(id.begin(), id.end(), x) - id.begin() + 1;
}

int lowbit(int x)
{
    return x & -x;
}

int quary(int x)
{
	int ans = 0;

	while(x > 0){
		ans += bits[x];
		x -= lowbit(x);
	}

	return ans;
}

void update(int x, int v)
{
	while(x <= len){
		bits[x] += v;
		x += lowbit(x);
	}
}

void build()
{
    block = sqrt(n);
    num = n / block;
    if(n % block){
        num ++;
    }
    for(int i = 1; i <= n; i ++){
        bo[i] = (i - 1) / block + 1;
    }
    for(int i = 1; i <= num; i ++){
        bl[i] = (i - 1) * block + 1;
        br[i] = i * block;
    }
    br[num] = n;
    for(int i = 1; i <= num; i ++){
        for(int j = bl[i]; j <= br[i]; j ++){
            cp[j] = ma[j];
        }
        sort(cp + bl[i], cp + br[i] + 1);
    }
}

void quary_block(int l, int r, int v, int t)	///       ， ma[l]  ans--     ma[r]  ans++             
{
	int x = bo[l];
	int y = bo[r];

	if(x == y){
		for(int i = l; i <= r; i ++){
			if(ma[i] < v){
				ans -= t;
			}
			else if(ma[i] > v){
				ans += t;
			}
		}
	}
	else{
		for(int i = l; i <= br[x]; i ++){
            if(ma[i] < v){
				ans -= t;
			}
			else if(ma[i] > v){
				ans += t;
			}
        }
        for(int i = x + 1; i < y; i ++){
	        ans -= t * (lower_bound(cp + bl[i], cp + br[i] + 1, v) - cp - bl[i]);
	    	ans += t * ((br[i] - bl[i] + 1) - (upper_bound(cp + bl[i], cp + br[i] + 1, v) - cp - bl[i]));
	    }
        for(int i = bl[y]; i <= r; i ++){
            if(ma[i] < v){
				ans -= t;
			}
			else if(ma[i] > v){
				ans += t;
			}
        }
	}
}

void exchange(int l, int r)
{
    if(l > r){
        return ;
    }
	int t;
	int opx;
	int opy;
	int x = bo[l];
	int y = bo[r];

    if(ma[l] < ma[r]){
        ans ++;
    }
    else if(ma[l] > ma[r]){
        ans --;
    }
	swap(ma[l], ma[r]);
	opx = lower_bound(cp + bl[x], cp + br[x] + 1, ma[l]) - cp;
	opy = lower_bound(cp + bl[y], cp + br[y] + 1, ma[r]) - cp;
	cp[opx] = ma[r];
	cp[opy] = ma[l];
	t = opx;
	while(t - 1 >= bl[x] && cp[t - 1] > cp[t]){
		swap(cp[t], cp[t - 1]);
		t --;
	}
	while(t <= br[x] && cp[t + 1] < cp[t]){
		swap(cp[t], cp[t + 1]);
		t ++;
	}
	t = opy;
	while(t - 1 >= bl[y] && cp[t - 1] > cp[t]){
		swap(cp[t], cp[t - 1]);
		t --;
	}
	while(t <= br[y] && cp[t + 1] < cp[t]){
		swap(cp[t], cp[t + 1]);
		t ++;
	}
}

int main(int argc, char const *argv[])
{
	while(scanf("%d", &n) == 1){
		ans = 0;
		memset(bits, 0, sizeof(bits));
		for(int i = 1; i <= n; i ++){
			scanf("%d", &ma[i]);
			id.pb(ma[i]);
		}
		sort(id.begin(), id.end());
    	id.erase(unique(id.begin(), id.end()), id.end());
    	len = id.size();
		for(int i = 1; i <= n; i ++){
            update(getid(ma[i]), 1);
			ans += i - quary(getid(ma[i]));
		}
		printf("%d
", ans);
		scanf("%d", &m);
		for(int i = 0; i < m; i ++){
			int l, r;

			scanf("%d%d", &l, &r);
			if(r < l){
                swap(r,l);
			}
			quary_block(l + 1, r - 1, ma[l], 1);
			quary_block(l + 1, r - 1, ma[r], -1);
			exchange(l, r);
			printf("%d
", ans);
		}
	}


	return 0;
}