1613. For Fans of Statistics
Time limit: 1.0 second
Memory limit: 64 MB Have you ever thought about how many people are transported by trams every year in a city with a ten-million population where one in three citizens uses tram twice a day?
Assume that there are n cities with trams on the planet Earth. Statisticians counted for each of them the number of people transported by trams during last year. They compiled a table, in which
cities were sorted alphabetically. Since city names were inessential for statistics, they were later replaced by numbers from 1 to n. A search engine that works with these data must be able to answer quickly a query of the following type: is there
among the cities with numbers from l to r such that the trams of this city transported exactly x people during last year. You must implement this module of the system.
InputThe first line contains the integer n, 0 < n < 70000. The second line contains statistic data in the form of a list of integers separated with a space. In this list, the ith
number is the number of people transported by trams of the ith city during last year. All numbers in the list are positive and do not exceed 109 ? 1. In the third line, the
number of queries q is given,
OutputOutput a string of length q in which the ith symbol is “1” if the answer to the ith query is affirmative, and “0” otherwise.
Sample
Problem Author: Alexander Ipatov
Problem Source: The 12th Urals Collegiate Programing Championship, March 29, 2008 Tags: data structures
)
|
题意
给你n个数字，编号从1开始。 然后m个查询，问你l到r编号中有没有num这个数字。
做法
把相同的数字的编号放在一起。 然后查询时，通过那个 map 那个数字，找到 对应的那些编号。然后二分 找最小的，但是大于等于l的数字，然后在判断这个数字是不是小于r。 如果都满足，就输出1，否者0,
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
map<int,set<int> >my;
int main()
{
int n,tem;
while(cin>>n)
{
my.clear();
for(int i=1;i<=n;i++)
{
cin>>tem;
my[tem].insert(i);
}
int m,l,r,num;
cin>>m;
for(int i=0;i<m;i++)
{
cin>>l>>r>>num;
int flag=0;
if(my.count(num))
{
set<int>::iterator it=my[num].lower_bound(l);
if(it!=my[num].end())
if(*it<=r)
flag=1;
}
printf("%d",flag);
}
puts("");
}
return 0;
}
URAL 1613. For Fans of Statistics 二分+stl
原文：http://blog.csdn.net/u013532224/article/details/44543029