首页 » 树状数组 » 正文

Team Rocket(线段树/树状数组)

牛客网暑期ACM多校训练营(第六场)Team Rocket

来源:https://www.nowcoder.com/acm/contest/144/I

题目描述

There are n trains running between Kanto and Johto region. Assuming the railway is a number line, the i-th train travels from coordinate li to coordinate ri (both inclusive).
One day, m Team Rocket members invaded the railway system successfully. The i-th Team Rocket member was going to destroy the transportation hub with coordinate xi. Once a transportation hub within the driving range of a train is destroyed, the train’s itinerary will be canceled immediately.
Giovanni wants to know how many train trips will be firstly canceled after each attack.
After all the attacks finished, for each train Giovanni needs to know that in which attack its itinerary was firstly canceled, or it was unaffected at all.

输入描述:

The input starts with one line containing exactly one integer T, which is the number of test cases.

For each test case, the first line contains two integers n and m, indicating the number of trains and the number of Team Rocket members.

Each of the next n lines contains 2 integers li and ri, indicating the driving range of the i-th train.

Each of the next m lines contains exactly one integer yi. , where xi is the transportation hub that Team Rocket members would destroy in the i-th attack, resi-1 is the product of the indexes of trips cancelled by the (i-1)-th attack and  means exclusive or. 

If no such trip exists, resi-1 is considered to be 0.

- 1 ≤ T ≤ 5.
- 1 ≤ n,m ≤ 2 x 105.
- -109 ≤ li ≤ ri ≤ 109.
- -109 ≤ xi ≤ 109.

输出描述:

For each test case, output one line "Case #x:" first, where x is the test case number (starting from 1).

Then output m lines, each line of which contains exactly one integer, indicating the number of train trips firstly canceled after the i-th attack.

Finally output one line, containing n integers, where the i-th integer is the time when the i-th train trip is firstly canceled or 0 if it is not affected.

示例1

输入

1
3 4
1 3
2 6
-999 1000000000
-1000
1
5
2

输出

Case #1:
0
2
1
0
2 3 2

总结

主要是将 [ l , r ] 区间变为 arr [ l ] = r 这里不懂,想通了就很好解决。

代码

线段树,使用的标程

#include<bits/stdc++.h>
#define ls(x) ((x)<<1)
#define rs(x) (ls(x)|1)
#define mid ((l+r)>>1)
#define lch ls(x), l, mid
#define rch rs(x), mid+1, r

using namespace std;  

const int MAXN = (1<<18)+21;  
const int mod = 998244353 ;  
int T,N,M, ans[MAXN], a[MAXN], tot;  
pair<int, int> seg[MAXN];  
struct cmp{
    bool operator()(const int &x, const int &y){
        return seg[x].second < seg[y].second;  
    }
};

vector<int> vec[MAXN<<2];  
#define ALL(x) vec[x].begin(), vec[x].end()

int ROUND_UP(int n){   //对齐,为了建线段树 
    int res=1;  
    while(res < n) res <<=1;  
    return res;  
}

int qi, ql, qr, last;  

int query(int x, int l, int r){
    if(r <= ql){  //已经完全在这个区间内了 
        int res = 0;  
        while(!vec[x].empty() && seg[vec[x].back()].second >= qr){
            if(!ans[vec[x].back()]){
                ++res;  
                ans[vec[x].back()] = qi;  
                last = int(1ll * last *vec[x].back()%mod); 
            }
            vec[x].pop_back();  
        }
        return res;  
    }
    int res = query(lch);  
    if(ql > mid) res += query(rch);  
    return res;  
}

void testCase(){
    static int CaseID = 0;  
    scanf("%d%d", &N, &M);  
    for(int i=1;i<=N;i++){  //输入区间,存入seg 
        scanf("%d%d", &seg[i].first, &seg[i].second);  
        a[i] = seg[i].first;  //为了离散化 
        ans[i]=0;  //记录第几次删除 
    }

    sort(a+1,a+1+N);  //排序 
    tot = int(unique(a+1, a+1+N)-(a+1));  //去重
    int n = ROUND_UP(tot);  //改成2的次方形式,以建立线段树 
    for(int i=1;i<=N;i++){
        int rk=int(lower_bound(a+1, a+1+tot, seg[i].first) - a);  //离散化点后将区间以点的形式放入vector 
        vec[n+rk-1].push_back(i);  
    } 

    for(int i=0;i<N;i++){  //将点所含区间以右边进行排序 
        sort(ALL(i+n),cmp());  
    }

    for(int i=n-1; i; --i){  
        vec[i].resize(vec[ls(i)].size()+ vec[rs(i)].size());  //设置长度为左右孩子节点的和 
        merge(ALL(ls(i)), ALL(rs(i)), vec[i].begin(), cmp());  //将左右的值放入父节点 
    }

    last=0;  
    printf("Case #%d: \n", ++CaseID);  
    for(qi=1; qi <= M; qi++){
        scanf("%d", &qr);  
        qr ^= last;  
        last=1;  
        ql = int (upper_bound(a+1, a+1+tot, qr) -a-1);  //离散化,减了1,是小于 
        int res = ql?query(1,1,n):0;  
        printf("%d\n", res);  
        if(!res)last=0;  //没删,赋值0 
    }

    for(int i=1; i<=N;i++){
        printf("%d%c", ans[i], " \n"[i == N]);  //骚操作 
    }
    for(int i=1;i<(n<<1);i++){  //逐个清除内存 
        vector<int>().swap(vec[i]);  
    }
}

int main(){
    //freopen("1.txt", "r", stdin);
    scanf("%d", &T);  
    while(T--)testCase();  
    return 0;  
}

树状数组的一个代码,不过采用的判断是否删除

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
#include <set>
#include <map>
#include <vector>
#define llt long long
using namespace std;
/******
   有n个区间,m次操作: 给数b问删去包含x=b^(resi-1%mod)的区间数,和区间什么时候删除的。
   resi-1记录的是上一次删除点的标号的乘积。

*/

//upper_bound() 查询 第一个大于 num的位置,没有就输出end()

const int N = 2e5+777;
const int INF = 1e9+7777;
const llt mod = 998244353;
int A[N],Cnt[N];//A[i]记录:原输入第i个区间线段,第几次删去
                //Cnt[i]记录: 第i次删去多少个区间线段
struct node{
    int l,r;
    int id;//保存以前的编号
}p[N];

int c[N];
int n,m;

void mkStree(){
    for(int i=1;i<=n;++i)
        c[i] = i;
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;j+=j&(-j))
            if(p[c[j]].r<p[c[i]].r) c[j] = c[i];
}
void modify(int pos){
    /*修改c[pos]及包括出pos位的值*/
    for(int x=pos;x<=n;x+=x&(-x)){
        c[x] = x;
        for(int y=1;y<(x&(-x));y<<=1)
            if(p[c[x]].r<p[c[x-y]].r) c[x] = c[x-y];
    }

}

/*查询[1,x]上的最大值*/
int query(int x){
    int id = 0;
    for(;x>0;x-=x&(-x))
        if(p[id].r<p[c[x]].r) id = c[x];
    return id;
}
/*节点按l排序,离散化l,而r即为数组的值*/
bool cmp(const node  &a,const node  &b){return a.l<b.l||(a.l==b.l&&a.r<b.r);}


void init(){
     memset(A,0,sizeof(A));
     memset(Cnt,0,sizeof(Cnt));

     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;++i){
         scanf("%d%d",&p[i].l,&p[i].r);
         p[i].id = i;
     }
     p[0].r = -INF;
     sort(p+1,p+1+n,cmp);//正式将l离散化为数组编号
//     for(int i=1;i<=n;++i){
//        printf("Point: %d %d\n",p[i].l,p[i].r);
//
//     }
     mkStree();
}
int main(){
    int cas;
    scanf("%d",&cas);
    for(int k=1;k<=cas;++k){
        init();
        node a;
        a.r = INF;
        int res = 0;
        for(int i=1;i<=m;++i){
            scanf("%d",&a.l);
            a.l ^=res;
            //cout<<i<<" "<<a.l<<endl;
            res = 1;
            if(p[1].l>a.l) {//删去的x位于所有区间的右侧
                //Cnt[i] = 0;
                res = 0;
            }else{
                int R = upper_bound(p+1,p+1+n,a,cmp)-p-1;
                /*查询[1,R]中r的最大值的下标id*/
                while(true){
                    int id = query(R);
                     //cout<<"i: "<<i<<" "<<id<<" "<<p[id].l<<" "<<p[id].r<<endl;
                    if(p[id].r<a.l) break;
                    /*线段p[id].id删去*/
                    res = 1LL*res*p[id].id%mod;
                    A[p[id].id] = i;
                    ++Cnt[i];
                    p[id].r = -INF;
                    modify(id);
                }
                if(Cnt[i]==0) res = 0;
            }

        }
        printf("Case #%d:\n",k);
        for(int i=1;i<=m;++i) printf("%d\n",Cnt[i]);
        for(int i=1;i<=n;++i) printf("%d%c",A[i]," \n"[i==n]);
    }
    return 0;
}

发表评论

7 + 1 =