Stone的txl数

阳光穿透心脏的1/2处 2022-07-12 08:05 8阅读 0赞

### Stone的txl数 ###

Time Limit: 1000MS  Memory Limit: 65536KB

[Submit][]  [Statistic][]

#### Problem Description ####

Stone 将一个序列中 m 个区间的和命名为 txl 数（区间重叠部分只取一次）。

现在，Stone 从 QAQ 的桌子上获得了一个序列，他想知道这个序列的 txl 数是多少。

#### Input ####

输入数据有多组（数据组数不超过 50），到 EOF 结束。

每组数据第一行为两个数 n, m (1 <= n <= 10^5, 1 <= m <= 1000)，分别代表序列的长度和区间的个数。

第二行为 n 个数代表该序列，(1 <= a\[i\] <= 10^7)；接下来 m 行每行两个数 l, r (1 <= l <= r <= n)，代表区间 \[l, r\]。

#### Output ####

对于每组数据，输出一行，表示该序列的 txl 数。

#### Example Input ####

10 3
    1 2 3 4 5 6 7 8 9 10
    1 3
    2 4
    3 5

#### Example Output ####

#### Hint ####

#### Author ####

「2016级ACM集训队第二次选拔赛」Stone

###     ###

\#include <stdio.h>  
\#include <stdlib.h>  
long long int  a\[10000005\],s;  
int main()  
\{  
    int n,m,x,y,X,Y,k,j;  
    while(scanf("%d%d",&n,&m)!=EOF)  
    \{  
        for(j=1; j<=n; j++)  
            scanf("%lld",&a\[j\]);  
         s=0;  
        scanf("%d%d",&x,&y);  
        for(k=x; k<=y; k++)  
        \{  
            s=s+a\[k\];  
        \}  
        for(j=0; j<m-1; j++)  
        \{  
            scanf("%d%d",&X,&Y);  
            X=k;  
            for(k=X; k<=Y; k++)  
            \{  
                s=s+a\[k\];  
            \}  
        \}  
        printf("%lld\\n",s);  
  
  
    \}  
    return 0;  
\}  
//注重找规律，其实题还是比较简单的。/  
//对于第一个区间，我们单独讨论。  
//发现k的价值。

#include <stdio.h>
    int n, m, l, r;
    long long a[1000010], sum[1000010];
    struct node
    {
        int l, r;
    } lxt[1100];
     int i,j;
    void Sort(int l, int r)
    {
    
        for( i = l; i<=r-1; ++i)
        {
            int k = i;
            for( j = i+1; j<=r; ++j)
            {
                if(lxt[k].l>lxt[j].l)
                    k = j;
            }
            if(k!=i)
            {
                struct node temp = lxt[i];
                lxt[i] = lxt[k];
                lxt[k] = temp;
            }
        }
    }
    int main()
    {
        while(~scanf("%d%d", &n, &m))
        {
    
            sum[0] = 0;
            for( i = 1; i<=n; ++i)
            {
                scanf("%lld", &a[i]);
                sum[i] = sum[i-1]+a[i];
            }
            long long ans = 0;
            for(i = 0; i<m; ++i)
            scanf("%d%d", &lxt[i].l, &lxt[i].r);
            Sort(0, m-1);
            int ll = lxt[0].l, rr = lxt[0].r;
            for( i = 1; i<m; ++i)
            {
                if(lxt[i].l>rr)
                {
                    ans+=sum[rr]-sum[ll-1];
                    ll = lxt[i].l;
                    rr = lxt[i].r;
                }
                else if(lxt[i].l>=ll&&lxt[i].r>=rr)
                    rr = lxt[i].r;
            }
            ans+=sum[rr]-sum[ll-1];
            printf("%lld\n", ans);
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/1960/pid/3718.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/1960/pid/3718.html