contest2 （线段树）

发布时间：2020-12-13 23:37:28 所属栏目：Linux 来源：网络整理

导读：? C - C HDU - 3577 Chinese always have the railway tickets problem because of its‘ huge amount of passangers and stations. Now goverment need you to develop a new tickets query system. One train can just take k passangers. And each passan

C - C

HDU - 3577

Chinese always have the railway tickets problem because of its‘ huge amount of passangers and stations. Now goverment need you to develop a new tickets query system.
One train can just take k passangers. And each passanger can just buy one ticket from station a to station b. Each train cannot take more passangers any time. The one who buy the ticket earlier which can be sold will always get the ticket.

InputThe input contains servel test cases. The first line is the case number. In each test case:
The first line contains just one number k( 1 ≤ k ≤ 1000 ) and Q( 1 ≤ Q ≤ 100000 )
The following lines,each line contains two integers a and b,( 1 ≤ a < b ≤ 1000000 ),indicate a query.
Huge Input,scanf recommanded.OutputFor each test case,output three lines:
Output the case number in the first line.
If the ith query can be satisfied,output i. i starting from 1. output an blank-space after each number.
Output a blank line after each test case.Sample Input

Sample Output

Case 1:
1 2 3 5

#include <iostream>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include <stdio.h>
#include <string.h>
#define rep(i,n) for(int i = 0 ; i < (n) ; i++)
using namespace std;
const int N = 1100009 ;
int ans = 0,flag = 1;
int a[1000009],b[1000009];

struct Node{
    int l,r,val,lazy_tag ;
}tree[N * 4];

void build(int l,int r,int root)
{
    tree[root].l = l,tree[root].r= r ;
    tree[root].val = 0,tree[root].lazy_tag = 0;
    if(l == r)
        return ;
    int mid = (l + r) / 2 ;
    build(l,mid,root * 2);
    build(mid + 1,root * 2+1);
}

void pushdown(int root)
{
    tree[root * 2].lazy_tag += tree[root].lazy_tag ;
    tree[root * 2].val += tree[root].lazy_tag ;
    tree[root * 2 + 1].lazy_tag += tree[root].lazy_tag ;
    tree[root * 2 + 1].val += tree[root].lazy_tag;
    tree[root].lazy_tag = 0;
}
void update(int l,int root )
{
    if(tree[root].l >= l && tree[root].r <= r)
    {
        tree[root].lazy_tag += 1 ;//注意这里的lazy一定要+= 不能=1因为之前就有累计也要下传
        tree[root].val += 1 ;
        return ;
    }
    if(tree[root].lazy_tag)
        pushdown(root);
    int mid = (tree[root].l + tree[root].r) / 2 ;
    if(l <= mid)
        update(l,root * 2 );
    if(r > mid)
        update(l,root * 2 + 1);
    tree[root].val = max(tree[root * 2].val,tree[root*2+1].val) ;
}

int  query(int l,int root )
{
    if(tree[root].l >= l && tree[root].r <= r)
    {
        cout << tree[root].val <<endl ;
        return tree[root].val ;
    }
    if(tree[root].lazy_tag)
        pushdown(root);
    int mid = (tree[root].l + tree[root].r) / 2 ;
    //有return就不会向上回溯,返回的就是所需的区间值
    if(r <= mid)
        return query(l,root * 2);//如果查询区间在左边，往左走
    else if(mid < l)
    {
        return query(l,root * 2 + 1);//如果查询区间在右边，往右走
    }
    else
        return max(query(l,root * 2),query(mid + 1,root * 2+1));//如果区间两边都有交集，往值大的一边走
}



int main()
{
    int n ;
    cin >> n ;
    int cnt = 0 ;
    while(n--)
    {
        cnt++ ;
        int p,q,maxx = 0;
        scanf("%d%d",&p,&q);
        for(int i = 0 ; i < q ; i ++)
        {
            scanf("%d%d",&a[i],&b[i]);
            if(b[i] > maxx)
                maxx = b[i];
        }
        build(1,maxx,1 );
        cout << "Case " << cnt << ":" << endl ;
        rep(i,q)
        {
            if(query(a[i],b[i] - 1,1) < p)//题目有坑，左闭区间，右开区间
            {
                cout << i + 1 <<" ";
                update(a[i],b[i] - 1,1) ;
            }
        }
        cout << endl ;
        cout << endl ;
    }

    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!