noj 2068 爱魔法的露露 [线性扫一遍]

njczy2010

2068

Accepted

325MS

8052K

1450Byte

G++

2014-11-13 11:20:40.0

爱魔法的露露

时间限制(普通/Java) : 1200 MS/ 4000 MS 运行内存限制 : 65536 KByte
总提交 : 47 测试通过 : 3

描述

仙灵女巫露露，对于魔法的热忱可是超出常人，要是发现了什么上古遗留下的魔法，她总是想方设法地获得，然后研究分析。而最近，他又从邪恶小法师维嘉那里获得了一个“奇怪”的魔法卷轴；

这个魔法卷轴上有一大串数字，而且根据卷轴上的描述，这个魔法的威力指数来自于这一串数字中“魔法区间”的数量；

所谓“魔法区间”指的是一段连续的闭区间，且这段区间上的所有数字均不相同；

现在，露露想知道这个魔法的威力指数，你能帮帮她么？

输入

先输入一个正整数T，表示样例个数，1≤T≤10。

对于每一个样例，先输入一个正整数n，表示卷轴上的数字个数(1≤n≤10⁶)；

再输入n个整数，第i个数a_i，表示卷轴上第i个数（0≤a_i≤10⁶）。

输出

对于每个样例，输出一个正整数，即威力指数。

题目保证结果在int范围内。

样例输入

1
3
1 2 3

样例输出

提示

读入数据请使用 scanf()；
对于样例，共有{1},{2},{3},{1,2},{2,3},{1,2,3}，6个魔法区间，所以威力为6。

题目来源

yuman

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<string>

 #include<iostream>

 #include<set>

 #define maxi(a,b) (a)>(b)?(a):(b)

 #define mini(a,b) (a)<(b)?(a):(b)

 #define N 1000005

 #define mod 10000

 #define ll long long

 using namespace std;

 int T;

 int tot;

 set<int> s;

 int a[N];

 int n;

 int vis[N];

 void ini()

 {

     int i;

     tot=;

     //s.clear();

     scanf("%d",&n);

     for(i=;i<=n;i++){

         scanf("%d",&a[i]);

     }

     memset(vis,,sizeof(vis));

 }

 void solve()

 {

     int i,j;

     i=;j=;

     for(j=;j<=n;j++){

        // if(s.find(a[j])==s.end()){

         if(vis[ a[j] ]==){

             vis[ a[j] ]++;

         }

         else{

             //j--;

             break;

         }

     }

    // tot+=j-i+1;

     while(i<=n)

     {

         //s.erase(a[i]);

         vis[ a[i] ]--;

         tot+=j-i;

         //printf(" i=%d j=%d tot=%d\n",i,j,tot);

         i++;

         for(;j<=n;j++){

            // if(s.find(a[j])==s.end()){

             if(vis[ a[j] ]==){

                 vis[ a[j] ]++;

             }

             else{

                 //j--;

                 break;

             }

         }

     }

 }

 void out()

 {

     printf("%d\n",tot);

 }

 int main()

 {

    // freopen("data.in","r",stdin);

     scanf("%d",&T);

     while(T--)

    // while(scanf("%I64d",&n)!=EOF)

     {

         ini();

         solve();

         out();

     }

     return ;

 }

巴特西

noj 2068 爱魔法的露露 [线性扫一遍]

爱魔法的露露

最新文章

热门文章