首页 > 代码库 > Ural 1613 For Fans of Statistics（vector应用）

Ural 1613 For Fans of Statistics（vector应用）

2024-07-15 18:43:12   221人阅读

题目：

For Fans of Statistics
Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64

Description

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.

Input

The 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 10 9 ? 1. In the third line, the number of queries q is given, 0 < q < 70000. The next q lines contain the queries. Each of them is a triple of integers l, r, and x separated with a space; 1 ≤ l ≤ r ≤ n; 0 < x < 10 9.

Output

Output 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 Input

inputoutput
5
1234567 666666 3141593 666666 4343434
5
1 5 3141593
1 5 578202
2 4 666666
4 4 7135610
1 1 1234567

10101

这个题想多了。。这个方法想到过，但是想到了一种特殊数据，就是当好多数都一样的时候，然后每次遍历都要遍历好多，这样的话很容易就超时。。。一直没想出更好的办法，就搜了搜题解，结果都是这么做的。。。好吧。。

这题的思路就是哈希，利用vector和取模来解决冲突问题。然后找。

代码如下：

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include<algorithm>

using namespace std;
int a[710000];
struct node
{
    int x, num;
};
vector <node> vec[110000];
const int mod=1e5+7;
int main()
{
    int n, q, i, j, y, l, r, x;
    scanf("%d",&n);
    node tmp;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        tmp.x=a[i];
        tmp.num=i;
        vec[a[i]%mod].push_back(tmp);
    }
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d%d",&l, &r, &x);
        if(a[l]==x||a[r]==x)
        {
            printf("1");
            continue ;
        }
        int len=vec[x%mod].size(), flag=0;
        for(i=0;i<len;i++)
        {
            if(vec[x%mod][i].x==x&&vec[x%mod][i].num>=l&&vec[x%mod][i].num<=r)
            {
                flag=1;
                break;
            }
        }
        if(flag)
        {
            printf("1");
        }
        else
            printf("0");
    }
    printf("\n");
    return 0;
}



联系
我们