T1 clique

Sol
考场上降智了没写出来。。
把给定的参数\(W_i,X_i\)转换成区间\((X_i-W_i,X_i+W_i)\)，问题转化成求数轴上最多不重区间数。
把所有区间按右端点排序，枚举贪心获取即可。
Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2000010;
namespace io
{
    inline int read()
    {
        int x=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}
        while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
        return f?x:-x;
    }
    inline void print(int x)
    {
        static char s[20],len;
        len=0;
        if(x<0)putchar('-'),x=-x;
        if(x==0)
        {
            putchar('0');return;
        }
        while(x)
        {
            s[++len]=x%10;
            x/=10;
        }
        for(int i=len;i;i--)putchar(s[i]+'0');
        return;
    }
}

struct node
{
    int l,r;
    bool operator<(const node &x)const
    {
        if(r==x.r)return l<x.l;
        return r<x.r;
    }
}a[maxn];
int ans[maxn],n;
int main()
{
    freopen("clique.in","r",stdin);
    freopen("clique.out","w",stdout);
    using namespace io;
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read();
        a[i]=(node){x-y,x+y};
    }
    sort(a+1,a+n+1);
    int now=a[1].r,ans=1;
    for(int i=2;i<=n;i++)
    {
        if(a[i].l>=now)now=a[i].r,ans++;
    }
    print(ans);putchar('\n');
    return 0;
}

T2 num

Sol
每次取模都使一个数至少减半，打个标记记录区间最大值，如果小于模数就不取模，这样取至多\(log\ n\)次就不能再取。所以对于取模操作直接暴力取，其它线段树基操。
Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lson tr[rt].ls
#define rson tr[rt].rs
#define mid ((l+r)>>1)
const int maxn=100010;
namespace io
{
    inline int read()
    {
        int x=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}
        while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
        return f?x:-x;
    }
    inline void print(int x)
    {
        static char s[20],len;
        len=0;
        if(x<0)putchar('-'),x=-x;
        if(x==0)
        {
            putchar('0');return;
        }
        while(x)
        {
            s[++len]=x%10;
            x/=10;
        }
        for(int i=len;i;i--)putchar(s[i]+'0');
        return;
    }
}
int n,a[maxn],m;
struct node
{
    int ls,rs,sum,mx;
}tr[maxn<<2];
inline void pushup(int rt)
{
    tr[rt].mx=max(tr[lson].mx,tr[rson].mx);
    tr[rt].sum=tr[lson].sum+tr[rson].sum;
    return;
}
int gpc;
inline int build(int l,int r)
{
    int rt=++gpc;
    if(l==r)
    {
        tr[rt].mx=tr[rt].sum=a[l];
        return rt;
    }
    lson=build(l  ,mid);
    rson=build(mid+1,r);
    pushup(rt);return rt;
}
inline void update(int rt,int l,int r,int L,int R,int q)
{
    if(tr[rt].mx<q)return;
    if(l==r)
    {
        tr[rt].sum=tr[rt].mx=tr[rt].mx%q;
        return;
    }
    if(mid>=L)update(lson,l  ,mid,L,R,q);
    if(mid< R)update(rson,mid+1,r,L,R,q);
    pushup(rt);return;
}
inline void modify(int rt,int l,int r,int p,int q)
{
    if(l==r)
    {
        tr[rt].mx=tr[rt].sum=q;
        return;
    }
    if(p<=mid)modify(lson,l,mid,p,q);
    else modify(rson,mid+1,r,p,q);
    pushup(rt);return;
}
inline int query(int rt,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)return tr[rt].sum;
    int ans=0;
    if(mid>=L)ans+=query(lson,l  ,mid,L,R);
    if(mid< R)ans+=query(rson,mid+1,r,L,R);
    return ans;
}
signed main()
{
    freopen("mod.in","r",stdin);
    freopen("mod.out","w",stdout);
    using namespace io;
    n=read();m=read();
    for(int i=1;i<=n;i++)a[i]=read();
    if(n<=1000&&m<=1000)
    {
        while(m--)
        {
            int opt=read();
            if(opt==1)
            {
                int l=read(),r=read();
                int ans=0;
                for(int i=l;i<=r;i++)ans+=a[i];
                printf("%lld\n",ans);
            }else if(opt==2)
            {
                int l=read(),r=read(),x=read();
                for(int i=l;i<=r;i++)a[i]%=x;
            }else
            {
                int l=read(),r=read();
                a[l]=r;
            }
        }
        return 0;
    }
    build(1,n);
    while(m--)
    {
        int opt=read();
        if(opt==1)
        {
            int l=read(),r=read();
            print(query(1,1,n,l,r));putchar('\n');
        }else if(opt==2)
        {
            int l=read(),r=read(),x=read();
            update(1,1,n,l,r,x);
        }else 
        {
            int p=read(),q=read();
            modify(1,1,n,p,q);
        }
    }
    return 0;
}

number

Sol
设\(f(x,k)\)表示\((x,2x]\)中二进制表示出来恰好\(k\)个\(1\)的数的个数。
结论：\(f(x,k)\)单调不降。
证明：令\(x\)变成\(x+1\)，那么区间变为\((x+1,2x+2]\)，与之间区间的差距是少了\(x+1\)，多了\(2x+1\)和\(2x+2\)。而\(2x+2\)二进制表示出来就是在\(x+1\)右端加一个0，所以这两个数数字1的个数一样。得证。
由于\(m\leq 10^18\)，所以所有答案（除去\(k=1\)为无穷多）都在\(10^18\)以内。
那么只需要二分查找第一个和最后一个答案为\(m\)的值即可。
设\(g(x,k)\)表示前\(x\)个数二进制下1的个数为\(k\)的数的个数，那么显然\(f(x,k)=g(2x,k)-g(x,k)\)。
求\(g(x,k)\)可以把\(x\)二进制拆分开，从高到低枚举，当第\(i\)位上是\(x\)从高到低的第\(cnt\)个1的时候，\(g(x,k)+=C_i^{k-cnt}\)，表示前\(cnt-1\)位固定，第\(cnt\)位取0，后面选取\(k-cnt\)个1的方案数，累加求解。
由于\(i,k\leq 64\)，所以组合数可以通过杨辉三角预处理实现。
因为一些未知原因，\(spj\)会显示最后一个点第二个答案错误。

#include<bits/stdc++.h>
#define int long long
using namespace std;
namespace io
{
    inline int read()
    {
        int x=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}
        while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c&15),c=getchar();
        return f?x:-x;
    }
    inline void print(int x)
    {
        static char s[20],len;
        len=0;
        if(x<0)putchar('-'),x=-x;
        if(x==0)
        {
            putchar('0');return;
        }
        while(x)
        {
            s[++len]=x%10;
            x/=10;
        }
        for(int i=len;i;i--)putchar(s[i]+'0');
        return;
    }
}
const int maxn=100010,inf=4611686018427387904;
int T,m,k,ans;
int c[70][70];
inline void pre()
{
    for(int i=0;i<=63;i++)c[i][0]=1;
    for(int i=1;i<=63;i++)
    {
        for(int j=1;j<=63;j++)c[i][j]=c[i-1][j]+c[i-1][j-1];
    }
    return;
}
inline int g(int x)
{
    int cnt=0,ans=0;
    for(int i=62;~i;i--)
    {
        if((x>>i)&1)
        {
            if(k>=cnt)
            {
                ans+=c[i][k-cnt];
            }cnt++;
        }
    }
    return ans;
}
inline int f(int x)
{
    int ans=g(x<<1)-g(x);
    return ans;
}
signed main()
{
    freopen("number.in","r",stdin);
    freopen("number.out","w",stdout);
    using namespace io;
    T=read();pre();
    while(T--)
    {
        m=read();k=read();
        if(k==1)
        {
            if(m==1)
            {
                printf("1 -1\n");
            }
            continue;
        }
        int l=1,r=inf;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(f(mid)>=m)r=mid;
            else l=mid+1;
        }
        int ll=l,rr=inf;
        while(ll<rr)
        {
            int mid=(ll+rr+1)>>1;
            if(f(mid)>m)rr=mid-1;
            else ll=mid;
        }
        print(l);putchar(' ');print(ll-l+1);putchar('\n');
    }
    return 0;
}