头像

乐园的巫女




离线:11天前


最近来访(2)
用户头像
两栖生物
用户头像
2010


//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAXN=1e5+10;

inline int read(){
    int ans=0,t=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')t=-1;c=getchar();}
    while(isdigit(c)){ans=(ans<<3)+(ans<<1)+(c^48);c=getchar();}
    return ans*t;
}

inline int lowbit(int x)
{
    return x&(-x);
}



int n,m;
int a[MAXN];//输入的 
ll cf[MAXN];//差分 
ll tree[MAXN];//i* 




inline void add(ll a[],int x,int y)
{
    while(x<=n)
    {
        a[x]+=y;
        x+=lowbit(x);
    }
}

inline ll ask(ll a[],int x)
{
    ll ans=0;
    while(x)
    {
        ans+=a[x];
        x-=lowbit(x);
    }
    return ans;
}

inline ll sum(int x)
{
    return ask(cf,x)*(x+1)-ask(tree,x);
}

int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;++i)
    {
        a[i]=read();
    }

    for(int i=1;i<=n;++i)
    {
        cf[i]=a[i]-a[i-1];
        tree[i]=i*cf[i];
    }

    for(int x=1;x<=n;++x)
    {
        for(int i=x-1;i>=x-lowbit(x)+1;i-=lowbit(i))
        {
            cf[x]+=cf[i];
            tree[x]+=tree[i];
        }
    }

    while(m--)
    {
        int l,r,c;
        char op;
        op=getchar();
        while(op!='Q'&&op!='C') op=getchar();
        if(op=='Q')
        {
            l=read();
            r=read();
            printf("%lld\n",sum(r)-sum(l-1));
        }
        else
        {
            l=read();
            r=read();
            c=read();
            add(cf,l,c);
            add(cf,r+1,-c);
            add(tree,l,c*l);
            add(tree,r+1,-(r+1)*c);

        }
    }

    return 0;
}


活动打卡代码 AcWing 260. 买票

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int ans=0,t=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')t=-1;c=getchar();}
    while(isdigit(c)){ans=(ans<<3)+(ans<<1)+(c^48);c=getchar();}
    return ans*t;
}

inline int lowbit(int x)
{
    return x&(-x);
}

const int MAXN=2e5+10;

int a[MAXN],tree[MAXN],ans[MAXN],num[MAXN];

int n;

inline void add(int x,int y)
{
    while(x<=n)
    {
        tree[x]+=y;
        x+=lowbit(x);
    }
} 

inline int ask(int x)
{
    int ans=0;
    while(x)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}

int main()
{
    while(scanf("%d",&n)!=EOF)
    {
///     printf("haha\n");
        memset(tree,0,sizeof(tree));
        for(int i=1;i<=n;++i)
        {
            a[i]=read();
            num[i]=read();
            add(i,1);
        }

//      printf("haha1\n");

        for(int i=n;i>=1;--i)
        {
            int l=1;
            int r=n;
            while(l<r)
            {
                int mid=(l+r)>>1;
                if(ask(mid)<=a[i]) l=mid+1;
                else r=mid;
            }
            ans[l]=num[i];
            add(l,-1);  
        }

//      printf("haha2\n");

        for(int i=1;i<=n;++i)
        {
            printf("%d ",ans[i]);
        }
        puts("");
//      printf("haha3\n");
    }
    return 0;
}


活动打卡代码 AcWing 244. 谜一样的牛

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int ans=0,t=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')t=-1;c=getchar();}
    while(isdigit(c)){ans=(ans<<3)+(ans<<1)+(c^48);c=getchar();}
    return ans*t;
}

inline int lowbit(int x)
{
    return x&(-x);
}

const int MAXN=2e5+10;

int a[MAXN],tree[MAXN],ans[MAXN];
int n,m;

inline void add(int x,int y)
{
    while(x<=n)
    {
        tree[x]+=y;
        x+=lowbit(x);
    }
}

inline int ask(int x)
{
    int ans=0;
    while(x)
    {
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}







int main()
{
    n=read();
    add(1,1);
    for(int i=2;i<=n;++i)
    {
        a[i]=read();
        add(i,1);
    }

    for(int i=n;i>=1;--i)
    {
        int l=1,r=n;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(ask(mid)<=a[i]) l=mid+1;
            else r=mid;
        }
        ans[i]=l;
        add(l,-1);
    }
    for(int i=1;i<=n;++i)
    {
        printf("%d\n",ans[i]);
    }


    return 0;
}


活动打卡代码 AcWing 257. 关押罪犯

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

const int MAXN=2e4+10;
const int MAXM=1e5+10;

struct relation
{
    int p1,p2,anger,p3,p4;
}a[MAXM];

void Quicksort(int L,int R)
{
    int key=a[(L+R)>>1].anger,i=L,j=R;
    while (i<=j)
    {
        while (a[i].anger>key) i++;
        while (a[j].anger<key) j--;
        if(i<=j)
        {
            swap (a[i],a[j]);
            i++;
            j--;
        }
    }
    while (i<=j);
    if (L<j) Quicksort (L,j);
    if (i<R) Quicksort (i,R);
}

int f[2*MAXN];

int findf(int x)
{
    return(f[x]=f[x]==x?x:findf(f[x]));
}

int main()
{
//  freopen("P1525_2.in","r",stdin);
//  freopen("test.out","w",stdout);
    int n,m;
    int ss,ee,aa;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&ss,&ee,&aa);
        a[i].p1=ss;
        a[i].p2=ee;
        a[i].p3=ss+n;
        a[i].p4=ee+n;
        a[i].anger=aa;
    }
    Quicksort(1,m);
    int now=0;
    int ans;
    for(int i=1;i<=2*n;++i)
    {
        f[i]=i;
    }
    while(++now<=m)
    {
        int f1=findf(a[now].p1);
        int f2=findf(a[now].p2);
        int f3=findf(a[now].p3);
        int f4=findf(a[now].p4);
        if(f1==f2)
        {
            printf("%d",a[now].anger);
            return 0;
        }
        f[f1]=f4;
        f[f2]=f3;
    }
    printf("%d",0);
    return 0;
}



//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;

inline int read(){
    int ans=0,t=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')t=-1;c=getchar();}
    while(isdigit(c)){ans=(ans<<3)+(ans<<1)+(c^48);c=getchar();}
    return ans*t;
}

inline int lowbit(int x)
{
    return x&(-x);
}

int n,m;
int tree[MAXN<<1];
int b[MAXN<<1];

inline void add(int x,int y)
{
    for(;x<=n;x+=lowbit(x))
    {
        b[x]+=y;
    }
}

inline int ask(int x)
{
    int ans=tree[x];
    for(;x;x-=lowbit(x))
    {
        ans+=b[x];
    }
    return ans;
}


int main()
{
    n=read();
    m=read();
    for(int i=1;i<=n;++i)
    {
        tree[i]=read();
    }
    for(int i=1;i<=m;++i)
    {
        char c;
        scanf("%c",&c);
        if(c=='C') 
        {
            int l=read();
            int r=read();
            int d=read();
            add(l,d);
            add(r+1,-d);
        }
        if(c=='Q')
        {
            int x=read();
            printf("%d\n",ask(x));
        }
    }

    return 0;
}


活动打卡代码 AcWing 147. 数据备份

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

inline int read(){
    int ans=0,t=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')t=-1;c=getchar();}
    while(isdigit(c)){ans=(ans<<3)+(ans<<1)+(c^48);c=getchar();}
    return ans*t;
}

const int MAXN=1e5+10;

int n,k,pr,ans;

struct gap{
    int val,l,r;
}g[MAXN];

bool vis[MAXN];

void del(int x)
{
    g[x].l=g[g[x].l].l;
    g[x].r=g[g[x].r].r;
    g[g[x].l].r=x;
    g[g[x].r].l=x;
}

struct node{
    int val,num;
    bool operator < (const node &rhs)const
    {
        return val>rhs.val;
    }
};

priority_queue<node> q;

int main()
{
    n=read();
    k=read();
    pr=read();
    g[0].val=g[n].val=2e9+10;
    for(int i=1;i<n;++i)
    {
        int nowx=read();
        g[i].val=nowx-pr;
        g[i].l=i-1;
        g[i].r=i+1;
        pr=nowx;
        q.push((node){g[i].val,i});
    }

    while(k--)
    {
        while(vis[q.top().num]) q.pop();
        node nowx=q.top();
        q.pop();
        int val=nowx.val;
        int num=nowx.num;
        ans+=val;
        vis[g[num].l]=1;
        vis[g[num].r]=1;
        g[num].val=g[g[num].l].val-g[num].val+g[g[num].r].val;
        q.push((node){g[num].val,num});
        del(num);
    }

    printf("%d",ans);

    return 0;
 } 


活动打卡代码 AcWing 150. 括号画家

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+10;

typedef pair<int,char> pic;

stack<pic>st;

char a[MAXN];

int ans;

int main()
{
    scanf("%s",&a);
    int nowx=0;
    while(a[nowx])
    {
        if(st.empty())
        {
            st.push({nowx,a[nowx]});
//          printf("push1\n");
            nowx++;
            continue;
        }
        char top=st.top().second;
        char c=a[nowx];
        if((top=='['&&c==']')||(top=='('&&c==')')||(top=='{'&&c=='}'))
        {
            st.pop();
//          printf("pop\n");
            if(!st.empty())
            {
//              printf("1 ans=max(%d,%d)\n",ans,nowx-st.top().first);
                ans=max(ans,nowx-st.top().first);
            }
            else
            {
//              printf("2 ans=max(%d,%d)\n",ans,nowx+1);
                ans=max(ans,nowx+1);
            }
        }
        else
        {
            st.push({nowx,a[nowx]});
//          printf("push2 nowx=%d\n",nowx);
        }
        nowx++;
    }


    printf("%d",ans);


    return 0;
}


活动打卡代码 AcWing 155. 内存分配

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;

inline int read(){
    int ans=0,t=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')t=-1;c=getchar();}
    while(isdigit(c)){ans=(ans<<3)+(ans<<1)+(c^48);c=getchar();}
    return ans*t;
}

queue<pii> waiting;//等待队列,first:占用内存长度 second:占用时间(p) 
set<pii> running;//正在进行的进程,first:地址 second:长度 
priority_queue<pii,vector<pii>,greater<pii> > release_order;
//小根堆,维护释放顺序。 first:释放时刻 second:地址 

int n;
int t,m,p;
int ans;//全部进程都运行完毕的时刻 
int been_put;//被放入过等待队列的进程总数 

bool allocate(int t,int m,int p)
{
    for(auto it=running.begin(); it!=running.end(); it++)
    {
        auto itt=it;
        itt++;
        if(itt!=running.end())
        {
            int nowx=it->first+it->second;
            if(m<=itt->first-nowx)
            {
                running.insert({nowx,m});
                release_order.push({t+p,nowx});
                return true;
            }
        }
    }
    return false;
}

void release(int nowtime)
{
    while(!release_order.empty()&&release_order.top().first<=nowtime)
    {
        int t=release_order.top().first;
        while(!release_order.empty()&&release_order.top().first==t)
        {
            auto nowtop=release_order.top();
            release_order.pop();
            auto it=running.lower_bound({nowtop.second,0});
            running.erase(it);
        }

        ans=t;

        while(!waiting.empty())
        {
            auto nowfront=waiting.front();
            if(allocate(t,nowfront.first,nowfront.second)) waiting.pop();
            else break;
        }
    }
}


int main()
{
    n=read();
    t=read();m=read();p=read();
    running.insert({-1,1});
    running.insert({n,1});
    while(t||m||p)
    {
        release(t);
        if(!allocate(t,m,p))
        {
            waiting.push({m,p});
            been_put++;
        }
        t=read();m=read();p=read();
    }

    release(1e9+10);

    printf("%d\n%d",ans,been_put);

    return 0;
}


活动打卡代码 AcWing 162. 黑盒子

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<bits/stdc++.h>
using namespace std;

const int MAXN=3e4+10;

inline int read(){
    int ans=0,t=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')t=-1;c=getchar();}
    while(isdigit(c)){ans=(ans<<3)+(ans<<1)+(c^48);c=getchar();}
    return ans*t; 
}

priority_queue<int> big;//大根堆
priority_queue<int,vector<int>,greater<int> > small;//小根堆

int n,m;
int q1[MAXN];
int q2[MAXN];
int num/*get的时候堆里有几个数*/,pin/*到了get数组的第几个*/;
int now/*现在堆里面有几个数*/;

int main()
{
    m=read();n=read();
    for(int i=1;i<=m;++i)
    {
        q1[i]=read();
    }
    for(int i=1;i<=n;++i)
    {
        q2[i]=read();
    }

    while(pin<n)
    {
        num=q2[++pin];
        while(now<num)
        {
            now++;
            if(pin==1)
            {
                small.push(q1[now]);
                continue;
            }
            else if(q1[now]<=big.top())
            {
                int nowy=big.top();
                small.push(nowy);
                big.pop();
                big.push(q1[now]);
            }
            else
            {
                small.push(q1[now]); 
            }
        }
        int nowx=small.top();
        big.push(nowx);
        small.pop();
        int nd=big.top();
        printf("%d\n",nd);
    }


    return 0;
}


活动打卡代码 AcWing 149. 荷马史诗

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~