【cf305B&C】

2015.05.27 20:19 Wed | 19次阅读 | 旧日oi | 固定链接 | 源码

B题目大意,给定n<=200000个数,定义一段区间的权值为这段区间内的数的最小值,求长度为1~n的所有区间的最大值。
题解
用单调栈搞出以每个点为最小值能覆盖的最长区间,扔到树状数组里求最大值。

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 200005
using namespace std;
int n;
int a[N];
int l[N],r[N],len[N];
int st[N],top;
int c[N];
int lowbit(int x)
{
    return x&(-x);
}
void add(int x,int y)
{
    for(;x;x-=lowbit(x)) c[x]=max(c[x],y);
}
int query(int x)
{
    int mx=0;
    for(;x<=n;x+=lowbit(x)) mx=max(c[x],mx);
    return mx;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    st[top=0]=0;
    for(int i=1;i<=n;i++)
    {
        while(top&&a[st[top]]>=a[i]) top--;
        l[i]=st[top]+1;
        st[++top]=i;
    }
    st[top=0]=n+1;
    for(int i=n;i;i--)
    {
        while(top&&a[st[top]]>=a[i]) top--;
        r[i]=st[top]-1;
        st[++top]=i;
    }
    for(int i=1;i<=n;i++) 
    {
        len[i]=r[i]-l[i]+1;
        add(len[i],a[i]);
    }
    for(int i=1;i<n;i++) printf("%d ",query(i));
    printf("%d\n",query(n));
}
C题目大意,给定n个数,n<=200000,每个数小于等于500000,维护一个集合,每次加入或删除给定的某个数,操作数<=200000,求集合内互质的数的对数。
题解
50w以内的数最多只能分解为7个不同的质因数,所以我们可以考虑容斥原理,以加入x为例,ans+=x0个公约数的,-=x1个公约数的,+=x有两个公约数的……
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#define N 500005
using namespace std;
#define ll long long
ll n,m;
ll ans;
ll a[N],cnt[N];
bool vis[N];
vector<ll> v[N];
ll prime[N],np[N],tot;
void makeprime()
{
    for(int i=2;i<=500000;i++)
    {
        if(!np[i]) prime[++tot]=i;
        for(int j=1;j<=tot&&prime[j]*i<=500000;j++)
        {
            np[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
void dive(int x,int pos)
{
    for(int i=1;i<=tot&&prime[i]*prime[i]<=x;i++)
    if(x%prime[i]==0)
    {
        v[pos].push_back(prime[i]);
        while(x%prime[i]==0) x/=prime[i];
    }
    if(x>1) v[pos].push_back(x);
}
void dfs(int pos,int now,int mul,int flag,int num)
{
    if(now==v[pos].size())
    {
        if(flag==-1) cnt[mul]--;
        ans-=cnt[mul]*(num&1?1:-1)*flag;
        if(flag==1) cnt[mul]++;
        return;
    }
    dfs(pos,now+1,mul*v[pos][now],flag,num+1);
    dfs(pos,now+1,mul,flag,num);
}
int main()
{
    cin>>n>>m;makeprime();
    for(int i=1;i<=n;i++) 
    {
        scanf("%I64d",&a[i]);
        dive(a[i],i);
    }
    for(int x,i=1;i<=m;i++)
    {
        scanf("%d",&x);
        if(vis[x])
        {
            vis[x]=0;
            dfs(x,0,1,-1,0);
        }
        else
        {
            vis[x]=1;
            dfs(x,0,1,1,0);
        }
        printf("%I64d\n",ans);
    }
}```