题解 | #妄想集合#

妄想集合

https://ac.nowcoder.com/acm/contest/11180/D

题目描述

开始有 n 个可重集合，开始时每一个集合中都有一个数，有 m 个操作。

Quant l r x：往编号在 [l,r] 的每个集合中加入一个数 x。
Ask l r：询问能否从 [l,r]的集合中取出三个数使得他们能作为边长组成一个三角形（即最小两个和要大于最大的）。

输入样例

5 5
1 10 2 6 2
Ask 1 3
Quant 1 2 5
Ask 1 3
Quant 1 4 5
Ask 4 5

输出样例

NO
YES
YES

关于三角形与斐波那契数列的关系

结论：当数列中的所有数都是斐波那契数列中的数的时候，任意三个数不能组成三角形.(证明很简单我这里就略过了)

算法1

(线段树) $O (n l o g n + q)$

因为题目给出了一个条件：保证操作加入的数字和最开始的数字均为正整数且不超过 $1 0^{9}$ 所以我首先打了个表发现当i==45的时候数列的值超过了 $1 0^{9}$ ，所以由鸽笼原理可以知道如果我们集合中的数字超过了45个，那样一定可以组成三角形所以在这里对于Ask我们先求一下[l,r]的集合的数目，如果数目大于45则一定可以，小于3一定不行，如果数目在此之间的话我们只需要把集合中的数字取出来排序之后暴力枚举三个值能不能构成三角形在这里看上去时间复杂度很高，但是我们仔细想一想，因为保证了集合中的数字至少有一个所以我们枚举的集合数一定是小于等于45个的那样的时间复杂度最多也就是 $O (3$ x $45$ x $l o g 45)$ 最多不超过810其实很小的啦.

if(sum>=46)
{
    puts("YES");
    continue;
}
else if(sum<=2)
{
    puts("NO");
    continue;
}
else
{
    vector<int> tmp;
    for(int i=l;i<=r;i++)
    {
        for(auto t:v[i])
            tmp.push_back(t);
    }
    bool flag=false;
    sort(tmp.begin(),tmp.end());
    for(int i=0;i<tmp.size()-2;i++)
    {
        if(tmp[i]+tmp[i+1]>tmp[i+2])
        {
            flag=true;
            break;
        }
    }
    if(flag)puts("YES");
    else puts("NO");
}

之后就是线段树的板子啦区间求和

int query(int u,int l,int r) { //区间求和
	if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;
	int mid=tr[u].l+tr[u].r>>1;
	int sum=0;
	if(l<=mid) sum+=query(2*u,l,r);
	if(r>mid) sum+=query(2*u+1,l,r);
	return sum;
}

单点修改

void modify(int u,int l,int r,int x) { //区间内的单点修改
	if(tr[u].sum/(tr[u].r-tr[u].l+1)>=46) return;//注意这里啊！！！没有的话就会tle
	//这句话的意思就是如果这一刻子树中所有的集合size都大于等于46了其实就没必要再查下去了 直接return就可以了
	if(tr[u].l==tr[u].r) {
		v[r].push_back(x);
		tr[u].sum++;
		return ;
	}
	int mid=tr[u].l+tr[u].r>>1;
	if(r<=mid) modify(2*u,l,r,x);
	else if(l>mid) modify(2*u+1,l,r,x);
	else {
		modify(2*u,l,mid,x);
		modify(2*u+1,mid+1,r,x);
	}
	pushup(u);
}

完整代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

typedef long long ll;

const int N=1e5+10;

struct node {
	int l,r,sum;//线段树中维护集合的size
} tr[4*N];
vector<int> v[N];//存放每个集合里面的元素
int n,m;

void pushup(int u) {
	tr[u].sum=tr[2*u+1].sum+tr[2*u].sum;
}

void build(int u,int l,int r) {
	tr[u]= {l,r};
	if(l==r) {
		tr[u].sum=1;
		return;
	}
	int mid=l+r>>1;
	build(2*u,l,mid);
	build(2*u+1,mid+1,r);
	pushup(u);
}

int query(int u,int l,int r) { //区间求和
	if(l<=tr[u].l&&r>=tr[u].r) return tr[u].sum;
	int mid=tr[u].l+tr[u].r>>1;
	int sum=0;
	if(l<=mid) sum+=query(2*u,l,r);
	if(r>mid) sum+=query(2*u+1,l,r);
	return sum;
}

void modify(int u,int l,int r,int x) { //区间内的单点修改
	if(tr[u].sum/(tr[u].r-tr[u].l+1)>=46) return;
	if(tr[u].l==tr[u].r) {
		v[r].push_back(x);
		tr[u].sum++;
		return ;
	}
	int mid=tr[u].l+tr[u].r>>1;
	if(r<=mid) modify(2*u,l,r,x);
	else if(l>mid) modify(2*u+1,l,r,x);
	else {
		modify(2*u,l,mid,x);
		modify(2*u+1,mid+1,r,x);
	}
	pushup(u);
}

int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		int t;
		scanf("%d",&t);
		v[i].push_back(t);
	}
	build(1,1,n);
	for(int T=0; T<m; T++) {
		string op;
		int l,r,x;
		cin>>op;
		scanf("%d %d",&l,&r);
		if(op[0]=='A') { //询问
			int sum=query(1,l,r);
			if(sum>=46) {
				puts("YES");
				continue;
			} else if(sum<=2) {
				puts("NO");
				continue;
			} else {
				vector<int> tmp;
				for(int i=l; i<=r; i++) {
					for(auto t:v[i])
						tmp.push_back(t);
				}
				bool flag=false;
				sort(tmp.begin(),tmp.end());
				for(int i=0; i<tmp.size()-2; i++) {
					if(tmp[i]+tmp[i+1]>tmp[i+2]) {
						flag=true;
						break;
					}
				}
				if(flag)puts("YES");
				else puts("NO");
			}
		} else {
			scanf("%d",&x);
			modify(1,l,r,x);
		}
	}
}

算法2

(并查集) $O (q$ x $46$ x $路径压缩)$

算法思路: 每次直接“暴力”的向[l,r]中加元素这里的暴力并不是真正的暴力，而是我每次加元素只需要加到下一个size()<=45的集合中去所以我们用并查集来维护每个元素的下一个元素是谁就可以啦

完整代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>

using namespace std;

const int N=1e5+10;
int f[N];
int n,m;
vector<int> v[N];

int find(int x)
{
    if(x!=f[x])
        f[x]=find(f[x]);
    return f[x];
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int t;
        scanf("%d",&t);
        v[i].push_back(t);
    }
    for(int i=1;i<N;i++) f[i]=i;//注意这里n的下一个是n+1所以只初始化到n是不够的
    while(m--)
    {
        string op;
        int l,r,k;
        cin>>op;
        scanf("%d %d",&l,&r);
        if(op[0]=='A')
        {
            int sum=0;
            bool flag=false;
            if(r-l+1>=46)
            {
                puts("YES");
                continue;
            }
            for(int i=l;i<=r;i++)
            {
                sum+=v[i].size();
            }
            if(sum>=46)
            {
                puts("YES");
                continue;
            }
            if(!flag)
            {
                vector<int> c;
                for(int i=l;i<=r;i++)
                {
                    for(auto t:v[i])
                        c.push_back(t);
                }
                sort(c.begin(),c.end());
                for(int i=0;i+2<c.size();i++)
//                 for(int i=0;i<c.size()-2;i++)这样写就wa了 因为c.size()是无符号数 所以在这里会有问题
//                  解决办法 1.加入特判if(c.size()<3) xxx
//                  2.强制类型转化 (int)c.size()-2
                {
                    if(c[i]+c[i+1]>c[i+2])
                    {
                        flag=true;
                        break;
                    }
                }
                if(flag)puts("YES");
                else puts("NO");
            }
        }
        else
        {
            scanf("%d",&k);
            for(int i=l;i<=r;i=find(i+1))
            {
                if(v[i].size()>=46)continue;
                v[i].push_back(k);
                if(v[i].size()==46) f[i]=find(i+1);
            }
        }
    }
}