[전체 2 점] [ZJOI 2013] bzoj 3110 K 대수 조회

제목 은 여기.
나무 커버 나무 문제 풀이 여기.
이거 맞 추고.하룻밤 이 또 지나 가 다 니...TAT
먼저 효율 을 말씀 드 리 겠 습 니 다. 제 트 리 는 283136 b 입 니 다. 7556 ms (영구 화 표기 의) 분 치 는 3148 b 이다. 1296 ms
_(:з)∠)_코드 길이 면.둘 다 차이 가 별로 없어 요. TT
생각:
전체 2 점 이 야.cdq 와 나 누 어 치료 하 는 것 이 매우 비슷 하 다.
내 이해 로 는...cdq 분 치 는 [l, mid] 업데이트 [mid + 1, r] 전체 2 분 에 따라 [l, mid] 질문 을 [l, mid] 또는 [mid + 1, r] 로 나 누 는 것 입 니 다.
어차피 사람 을 오도 하 든 말 든 상관 없어.
조건 abs (c) < = N 을 알 게 되면 우 리 는 가중치 에 따라 할 수 있 습 니 다.
solve (S, l, r) 를 정의 하면 집합 S 를 처리 하 는 작업 중 S 의 업데이트 작업 add (c) 의 c * 8712 ° [l, r] 질문 작업 의 답 ans * 8712 ° [l, r] 를 표시 하고 S 의 모든 작업 번호 가 상승 서열 임 을 보증 합 니 다.
그러면 우리 가 요구 하 는 것 은 바로 solve (1... M., - N. N) (in fact.. 데이터 에 마이너스 가 없다.....................................................
현재 solve 를 처리 하려 면 먼저 mid = (l + r) > > 1 로 나 누 십시오.
그리고 업데이트 작업 이 뚜렷 합 니 다.
질문 에 대해 서 는 먼저 명확 해 야 합 니 다!!크다어 릴 때 부터 K 번 째 가 아니 라!!!큰 것 부터 작은 것 까지!!!(나 는 여기 서 울 었 다 =)
그래서 분명히 우리 가 집계 해 야 할 것 은 이때 오른쪽 구역 에 몇 개가 있 는 지 입 니 다.
cnct 를 통계 하 는 방법 은 이 렇 습 니 다. 우 리 는 오른쪽 구역 에 대해 1 차원 트 리 배열 에서 직접 모 의 작업 을 합 니 다. 집합 S 의 순서 가 질서 가 있 기 때문에 조작 순 서 를 보장 할 수 있 습 니 다.
1 차원 트 리 배열 구간 업데이트 구간 조회 방법 여기
아 날로 그 가 끝 날 때마다 트 리 배열 은 비 워 야 하지만 시간 을 절약 하기 위해 서 는 조작 시간 을 기록 하면 됩 니 다.
그리고 우 리 는 현재 S 를 좌우 두 개의 집합 S1 S2 로 나 눈 후에 다시 돌아 가면 됩 니 다 = v =
S 가 비 었 을 때 마지막 경계 로 바로 돌아 가면 l = = r 일 때 ans 를 바로 업데이트 할 수 있 습 니 다!
신 갱: 이거!문제!아니!네!쓰다cin！와!cout！！！！！원래 동기 화 된 입 출력 을 취소 하고 RE TAT 를 계속 하 라 고 쓰 여 있 었 습 니 다.

#include "cstdio"
#define lowbit(x) (x & (-x)) 
 
using namespace std;
 
const int Nmax = 50005;
 
int N, M;
struct Option{
    int sign, x, y, c;
}op[Nmax];
 
int tot = -1, ans[Nmax];
int q[Nmax], tmp[2][Nmax];
 
namespace BIT{
    int t[Nmax][2], d[Nmax][2];
 
    void update(bool s, int pos, int c)
    {
        for (int i = pos; i <= N; i += lowbit(i)) {
            if (t[i][s] != tot) { t[i][s] = tot; d[i][s] = 0; }
            d[i][s] += c;
        }
    }
     
    int get_sum(bool s, int pos)
    {
        int res = 0;
        for (int i = pos; i; i -= lowbit(i)) {
            if (t[i][s] != tot) { t[i][s] = tot; d[i][s] = 0; }
            res += d[i][s];
        }
        return res;
    }
     
    void Add(int x, int y)
    {
        update(0, x, 1); update(0, y + 1, -1);
        update(1, x, x); update(1, y + 1, -(y + 1));
    }
     
    int Query(int x, int y)
    {
        int temp = get_sum(0, y) * (y + 1) - get_sum(1, y);
        temp -= get_sum(0, x - 1) * x - get_sum(1, x - 1);
        return temp;
    }
}
 
void solve(int L, int R, int l, int r)
{
    if (L > R) return;
     
    ++tot; int mid = (l + r) >> 1;
    if (l == r) {
        for (int i = L; i <= R; ++i) if (op[q[i]].sign == 2) ans[q[i]] = mid;
        return;
    }
     
    tmp[0][0] = tmp[1][0] = 0; using namespace BIT;
    for (int i = L; i <= R; ++i) {
        int temp = q[i];
        if (op[temp].sign == 1) {
            if (op[temp].c <= mid) tmp[0][++tmp[0][0]] = temp;
            else {
                tmp[1][++tmp[1][0]] = temp;
                Add(op[temp].x, op[temp].y);
            }
        } else {
            int cnt = Query(op[temp].x, op[temp].y);
            if (cnt < op[temp].c) {
                op[temp].c -= cnt;
                tmp[0][++tmp[0][0]] = temp;
            } else tmp[1][++tmp[1][0]] = temp;
        }
    }
     
    int tl = L, t2 = L + tmp[0][0] - 1;
    for (int i = 1; i <= tmp[0][0]; ++i) q[tl++] = tmp[0][i];
    for (int i = 1; i <= tmp[1][0]; ++i) q[tl++] = tmp[1][i];
    solve(L, t2, l, mid); solve(t2 + 1, R, mid + 1, r);
}
 
int main()
{
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i) {
        scanf("%d%d%d%d", &op[i].sign, &op[i].x, &op[i].y, &op[i].c);
        q[i] = i;
    }
    solve(1, M, 1, N);
    for (int i = 1; i <= M; ++i) {
        if (op[i].sign == 2) printf("%d
", ans[i]);
    }
     
    return 0;
}

맞다.사실 이 문 제 는 나무 모양 의 배열 을 쓸 필요 가 없다.STL 폭력 으로 살 수 있어...
출처:http://blog.csdn.net/qq_21110267/article/details/44514709

#include 
#include 
#include 
using namespace std;
const int maxn = 50000 + 10;

struct opt {
	int i, k, a, b, c;
	bool operator < (const opt& rhs) const {
		if(c == rhs.c) return i < rhs.i;
		return c > rhs.c;
	}
}A[maxn];

vector T;
int ID[maxn];
bool ins[maxn];

int main()
{
	int n, m;
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= m; i++) {
		int k, a, b, c;
		scanf("%d %d %d %d", &k, &a, &b, &c);
		A[i] = (opt){i, k, a, b, c};
		if(k == 1) T.push_back(A[i]);
	}
	sort(T.begin(), T.end());
	for(int i = 0; i < T.size(); i++) ID[T[i].i] = i;
	for(int i = 1; i <= m; i++)
		if(A[i].k == 1) ins[ID[i]] = 1;
		else {
			int j, c = 0;
			for(j = 0; j < T.size(); j++) if(ins[j]) {
				int len = min(A[i].b, T[j].b) - max(A[i].a, T[j].a) + 1;
				if(len <= 0) continue;
				if((c += len) >= A[i].c) break;
			}
			printf("%d
", T[j].c);
		}
	return 0;
}