数据结构测试2 on 2019.9.25

雨点打透心脏的1/2处 2023-06-04 08:53 16阅读 0赞

**又是一天的数据结构，但今天直接爆炸，1题和3题都写挂了200->0。**

**T1 abnormal**

**![1596060-20191001004107144-1649515524.png][]**

**一开始想的是线段树，但是自己感觉维护不来，果断放弃线段树。这时又想到离线的莫队做法，本以为这道题稳了，结果最后还是打炸了。题面意思都搞错了，真的是个傻逼。**

**这道题对于莫队来讲就是最简单的莫队，用一个数组cnt来维护每个魅力值的出现次数即可，但注意在统计出现次数的时候，还是要加注意，因为题目中定义的不正常团伙是只能出现2次，所以少于两次的和超过两次的都要累加他们的贡献。需要小小的特判。**

**代码如下：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    struct node{
        int l,r,id;
        long long ans;
    }mo[maxn*4];
    int belong[maxn];
    int block;
    bool cmp(node a,node b){
        return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
    } 
    int cnt[maxn];
    long long ans;
    int a[maxn];
    int vis[maxn];
    inline void add(int x){
        cnt[a[x]]++;
        if(cnt[a[x]]>3) ans+=a[x];
        else if(cnt[a[x]]==3) ans+=a[x]*cnt[a[x]];
        else if(cnt[a[x]]==2) ans-=a[x];
        else ans+=a[x];
    }
    inline void del(int x){
        cnt[a[x]]--;
        if(cnt[a[x]]>2) ans-=a[x];
        else if(cnt[a[x]]==2) ans-=3*a[x];
        else if(cnt[a[x]]==1) ans+=a[x];
        else ans-=a[x];
    }
    int n,m;
    long long all[maxn];
    int main(){
        scanf("%d%d",&n,&m);
        block=sqrt(n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            belong[i]=(i-1)/block+1;
            mo[i].id=i;
        }
        int l=1,r=0;
        for(int i=1;i<=m;i++) scanf("%d%d",&mo[i].l,&mo[i].r);
        sort(mo+1,mo+1+m,cmp);
        //for(int i=1;i<=m;i++) printf("%d %d\n",mo[i].l,mo[i].r); 
        for(int i=1;i<=m;i++){
            while(l<mo[i].l) del(l++);
            while(r>mo[i].r) del(r--);
            while(l>mo[i].l) add(--l);
            while(r<mo[i].r) add(++r);
            all[mo[i].id]=ans;
        }
        for(int i=1;i<=m;i++) printf("%lld\n",all[i]);
        return 0;
    }

**T2 irregular**

**![1596060-20191001004651774-1827240302.png][]**

**待改 dsu on tree**

**T3 unnormal**

**![1596060-20191001004811365-2143069475.png][]**

**中位数？直接大力平衡树。但是最后全wa?为什么，longlong乘的时候不乘1ll见祖宗。**

**但我唯一会的平衡树就是splay，splay常数又过大，这道题来讲最后一个点卡splay，怎么卡都卡不过。**

**90分代码如下（加了若干优化还是过不了）：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#pragma GCC optimize(1)
    #pragma GCC optimize(2)
    #pragma GCC optimize(3)
    #include<iostream>
    #include<cstdio>
    #include<ctime>
    #include<cstdlib>
    #include<cstring>
    #include<algorithm>
    #define Ri register int  
    #define sswap(x,y) x^=y^=x^=y;
    template <class T> T mmin(T x,T y){
         return(x)<(y)?(x):(y);}
    template <class T> T mmax(T x,T y){
         return(x)<(y)?(y):(x);}
    template <class T> T lowbit(T x){
         return ((x)&(-(x)));}
    typedef long long ll;
    using namespace std;
    namespace io{
        const int MT=5e7;
        char buf[MT];ll c,sz;
        void begin(){c=0;sz=fread(buf,1,MT,stdin);}
        template<class T>
        inline bool read(T &t) 
        {
            while(c<sz&&buf[c]!='-'&&(buf[c]<'0'||buf[c]>'9'))c++;
            if(c>=sz)return false;
            bool flag=0;if(buf[c]=='-')flag=1,c++;
            for(t=0;c<sz&&'0'<=buf[c]&&buf[c]<='9';c++)t=t*10+buf[c]-'0';
            if(flag==1)t=-t;return true;
        }
    }
    template <typename _TpInt>
    inline void write(_TpInt x)
    {
        if (x<0){
            putchar('-');
            write<_TpInt>(~x+1);
        }
        else {
            if (x>9)write<_TpInt>(x/10);   
            putchar(x%10+'0');
        }
    }
    const int maxn=1e6+7;
    const int inf=0x7fffffff;
    const int mod=1e9+7;
    int ch[maxn][2],fa[maxn],siz[maxn],cnt[maxn];
    long long key[maxn];
    int rt,sz;
    long long fi;
    long long sum;
    int a,b,c,n;
    long long min(long long a,long long b){
        return a<b?a:b;
    }
    bool check(int x){
        return ch[fa[x]][1]==x;
    }
    void pushup(int x){
        siz[x]=siz[ch[x][1]]+siz[ch[x][0]]+cnt[x];
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],who=check(x);
        ch[y][who]=ch[x][who^1];
        fa[ch[y][who]]=y;
        ch[x][who^1]=y;
        fa[y]=x,fa[x]=z;
        if(z) ch[z][ch[z][1]==y]=x;
        pushup(y);pushup(x);
    }
    void splay(int x){
        for(int f;(f=fa[x]);rotate(x)){
            if(fa[f]) rotate((check(x)==check(f))?f:x);  
        }
        rt=x;
    } 
    void insert(int x){
        if(!rt){
            rt=++sz;
            key[sz]=x;
            siz[sz]=cnt[sz]=1;
            return;
        }
        int now=rt,f=0;
        while(1){
            if(x==key[now]){
                cnt[now]++;
                pushup(f);
                pushup(now);
                splay(now);
                return;
            }
            f=now,now=ch[now][x>key[now]];
            if(!now){
                sz++;
                fa[sz]=f;
                siz[sz]=cnt[sz]=1;
                ch[f][x>key[f]]=sz;
                key[sz]=x;
                pushup(f);
                splay(sz);
                return;
            }
        }
    }
    long long rnk(int x){
        int now=rt;
        while(1){
            if(ch[now][0]&&x<=siz[ch[now][0]]) now=ch[now][0];
            else{
                int tmp=siz[ch[now][0]]+cnt[now];
                if(tmp>=x) return key[now];
                x-=tmp;
                now=ch[now][1];
            }
        }
    } 
    int main(){
        scanf("%d%d%d%d",&a,&b,&c,&n);
        insert(1);
        sum=1;
        for(int i=2;i<=n;i++){
            int wz=(i/2);
            long long mi=rnk(wz);
            fi=(long long)(1ll*a*mi+1ll*b*i+c)%mod;
            sum+=fi;
            insert(fi);
        }
        printf("%lld\n",sum);
        return 0;
    } 
    /*
    64582 34650 2040 100000
    41492359064511
    */

转载于:https://www.cnblogs.com/LJB666/p/11614644.html

[1596060-20191001004107144-1649515524.png]: /images/20230601/d7828b7c34f640ff92d5bbab136e6791.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/80497e8e8000414c950c16bd0742f8db.png
[1596060-20191001004651774-1827240302.png]: /images/20230601/034e9c8502ee4b9ca60d31381a39424b.png
[1596060-20191001004811365-2143069475.png]: /images/20230601/00e6472df0ed48658a15bcc762af432e.png