T1有多少人不是写的线段树。。

T1不是输出答案题吗?只要会用读入和输出基本都能A吧

不是离散化之后随便做吗？

这和线段树到底有何关系

用了一个set和一个multiset，20分QwQ

我，但是没过

不是STL练习题吗

没用线段树路过...

dengcha 数列

随便推推式子就可以了

我过了

作者：520Enterprise 链接：https://ac.nowcoder.com/discuss/335697?type=101&order=0&pos=1&page=1 来源：牛客网 #include<cmath> #include<cstdio> #include<iostream> #include<cstdlib> #include<algorithm> #include<cstring> #include<map> #include<queue> #include<set> #include<vector> #include<bitset> #define int __int128 #define ll __int128 using namespace std; const int maxn=300005; const long long mod=1e9+7; int n; ll k,sum,a[maxn],shika[maxn],f1,f2,f3,erci,yici,changshu; map<ll,ll>pre; inline ll read() {     ll x=0,f=1;     char ch=getchar();     while(ch<'0'||ch>'9')     {         if(ch=='-')             f=-1;         ch=getchar();     }     while(ch>='0'&&ch<='9')     {         x=(x<<1)+(x<<3)+(ch^48);         ch=getchar();     }     return x*f; } inline void write(ll a) {     if(a<0)     {         char a='-',b='1';         putchar(a);         putchar(b);     }     else     {         if(a>=10)             write(a/10);         putchar(a%10+'0');     } } void jiefangcheng(int f1,int f2,int f3) {     erci=(f3+f1-2*f2)/2;     erci%=mod;     yici=f2-f1-3*erci;     yici%=mod;     changshu=f1-erci-yici;     changshu%=mod; } signed main() {     n=read(),k=read();     for(int i=1;i<=n;++i)         a[i]=a[i+n]=a[i+2*n]=read();     for(int i=1;i<=3*n;++i)     {         if(pre.find(a[i])==pre.end())             pre[a[i]]=0;         shika[i]=(shika[i-1]+pre[a[i]])%mod; //      cout<<shika[i]<<' ';         sum=(sum+i*(i+1)/2-shika[i])%mod;         if(i==n)             f1=sum;         if(i==2*n)             f2=sum;         if(i==3*n)             f3=sum;         pre[a[i]]=i;     }     jiefangcheng(f1,f2,f3); //  cout<<f1<<' '<<f2<<' '<<f3<<endl; //  cout<<erci<<' '<<yici<<' '<<changshu<<endl;     write(((erci*k%mod*k%mod+yici*k%mod+changshu)%mod+mod)%mod);     return 0; } 90分求助

T1 。。。 我是树状数组的(滑稽

看见dalao们在装逼，不好说什么，爆零的我只好说一句： %%%

哎？线段树？OwO 大概是排序后离散化然后数学计算一下(计算过程O(N))就可以了呀？

对啊，hash or 基数排序 可以O(n)