[洛谷P3987]我永远喜欢珂朵莉~

摘要:
[Luogu P3987]我会一直喜欢Kodori ~主题的主旨是给你一些操作。操作包括以下两种类型:在间隔之间划分所有倍数。想法1:为范围内使用的每个素因子打开一个集合,以保持包含素因子的下标。对于运算,将分解素因子,并在集合中找到满足带下标的条件的数。如果在操作后不包括素因子,则将从集合中删除。对于操作,请使用树阵列进行维护。
[洛谷P3987]我永远喜欢珂朵莉~

题目大意:

给你(n(nle10^5))个数(A_{1sim n}(A_ile5 imes10^5))(m(mle5 imes10^5))次操作,操作包含以下两种:

  1. 将区间([l,r])间所有(v)的倍数除以(v)
  2. 求区间([l,r])所有数之和。

思路1:

对范围内要用到的每个质因数开一个set维护包含该质因子的(A_i)下标。

对于操作(1),将(v)分解质因数,在set中查找下标在([l,r])中的满足条件的数。并将这些数(div v)。若操作过后不包含该质因数,则将其从set中删去。

对于操作(2),用树状数组维护即可。

源代码1:

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<sys/mman.h>
#include<sys/stat.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
class MMapInput {
    private:
        char *buf,*p;
        int size;
    public:
        MMapInput() {
            register int fd=fileno(stdin);
            struct stat sb;
            fstat(fd,&sb);
            size=sb.st_size;
            buf=reinterpret_cast<char*>(mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));
            p=buf;
        }
        char getchar() {
            return (p==buf+size||*p==EOF)?EOF:*p++;
        }
};
MMapInput mmi;
inline int getint() {
    register char ch;
    while(!isdigit(ch=mmi.getchar()));
    register int x=ch^'0';
    while(isdigit(ch=mmi.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
typedef __gnu_pbds::tree<int,__gnu_pbds::null_type,std::less<int>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update> rbtree;
typedef long long int64;
const int N=1e5+1,M=1e5,A=1e6+1,P=78499;
bool vis[A];
int a[N],n,m,p[P],fail[N];
inline void sieve() {
    for(register int i=2;i<A;i++) {
        if(vis[i]) continue;
        p[++p[0]]=i;
        for(register int j=i*2;j<A;j+=i) {
            vis[j]=true;
        }
    }
}
rbtree set[P];
class FenwickTree {
    private:
        int64 val[N];
        int lowbit(const int &x) const {
            return x&-x;
        }
    public:
        void modify(int p,const int &x) {
            for(;p<=n;p+=lowbit(p)) val[p]+=x;
        }
        int64 query(int p) const {
            int64 ret=0;
            for(;p;p-=lowbit(p)) ret+=val[p];
            return ret;
        }
        int64 query(const int &l,const int &r) const {
            return query(r)-query(l-1);
        }
};
FenwickTree t;
int main() {
    sieve();
    n=getint(),m=getint();
    for(register int i=1;i<=n;i++) {
        a[i]=getint();
        t.modify(i,a[i]);
        int tmp=a[i];
        for(register int j=1;p[j]*p[j]<=tmp;j++) {
            if(tmp%p[j]==0) {
                set[j].insert(i);
                while(tmp%p[j]==0) {
                    tmp/=p[j];
                }
            }
        }
        if(tmp!=1) {
            set[std::lower_bound(&p[1],&p[p[0]]+1,tmp)-p].insert(i);
        }
    }
    for(register int tim=1;tim<=m;tim++) {
        const int opt=getint();
        const int l=getint(),r=getint();
        if(opt==1) {
            const int tmp=getint();
            int v=tmp;
            for(register int i=1;p[i]*p[i]<=v;i++) {
                if(v%p[i]!=0) continue;
                int sum=1;
                for(;v%p[i]==0;v/=p[i]) sum*=p[i];
                const rbtree::iterator begin=set[i].lower_bound(l);
                const rbtree::iterator end=set[i].upper_bound(r);
                if(v==1) {
                    for(rbtree::iterator it=begin;it!=end;) {
                        if(a[*it]%p[i]!=0) {
                            set[i].erase(it++);
                            continue;
                        }
                        if(a[*it]%tmp==0&&fail[*it]<tim) {
                            t.modify(*it,a[*it]/tmp-a[*it]);
                            a[*it]/=tmp;
                        }
                        it++;
                    }
                    continue;
                }
                for(rbtree::iterator it=begin;it!=end;) {
                    if(a[*it]%p[i]!=0) {
                        set[i].erase(it++);
                        continue;
                    }
                    if(a[*it]%sum!=0) fail[*it]=tim;
                    it++;
                }
            }
            if(v!=1) {
                const int i=std::lower_bound(&p[1],&p[p[0]]+1,v)-p;
                const rbtree::iterator begin=set[i].lower_bound(l);
                const rbtree::iterator end=set[i].upper_bound(r);
                for(rbtree::iterator it=begin;it!=end;) {
                    if(a[*it]%v!=0) {
                        set[i].erase(it++);
                        continue;
                    }
                    if(a[*it]%tmp==0&&fail[*it]<tim) {
                        t.modify(*it,a[*it]/tmp-a[*it]);
                        a[*it]/=tmp;
                    }
                    it++;
                }
            }
        }
        if(opt==2) {
            printf("%lld
",t.query(l,r));
        }
    }
    return 0;
}

思路2:

本题是某年CCF-CSP原题,用当时原题的数据,上面的做法是过不了的。

考虑不要按照质因数维护set,将操作离线,对于每个(v)维护一个set。然后卡卡常就过了。

源代码:

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<cstdio>
#include<cctype>
#include<vector>
#include<climits>
#include<sys/mman.h>
#include<sys/stat.h>
#include<ext/pb_ds/assoc_container.hpp>
class MMapInput {
	private:
		char *buf,*p;
		int size;
	public:
		MMapInput() {
			register int fd=fileno(stdin);
			struct stat sb;
			fstat(fd,&sb);
			size=sb.st_size;
			buf=reinterpret_cast<char*>(mmap(0,size,PROT_READ,MAP_PRIVATE,fileno(stdin),0));
			p=buf;
		}
		char getchar() {
			return (p==buf+size||*p==EOF)?EOF:*p++;
		}
};
MMapInput mmi;
inline int getint() {
	register char ch;
	while(!isdigit(ch=mmi.getchar()));
	register int x=ch^'0';
	while(isdigit(ch=mmi.getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
typedef long long int64;
const int N=1e5+1,M=1e5,A=5e5+1;
int n,a[N];
struct Opt {
	int type,l,r,v;
};
Opt o[M];
std::set<int> set[M];
std::vector<int> vec;
int id[A];
class FenwickTree {
	private:
		int64 val[N];
		int lowbit(const int &x) const {
			return x&-x;
		}
	public:
		void modify(int p,const int &x) {
			for(;p<=n;p+=lowbit(p)) val[p]+=x;
		}
		int64 query(int p) const {
			int64 ret=0;
			for(;p;p-=lowbit(p)) ret+=val[p];
			return ret;
		}
		int64 query(const int &l,const int &r) const {
			return query(r)-query(l-1);
		}
};
FenwickTree t;
int main() {
	n=getint();
	const int m=getint();
	for(register int i=1;i<=n;i++) {
		t.modify(i,a[i]=getint());
	}
	for(register int i=0;i<m;i++) {
		o[i].type=getint();
		o[i].l=getint();
		o[i].r=getint();
		if(o[i].type==1) {
			o[i].v=getint();
			if(o[i].v==1) continue;
			vec.push_back(o[i].v);
		}
	}
	std::sort(vec.begin(),vec.end());
	vec.resize(std::unique(vec.begin(),vec.end())-vec.begin());
	std::fill(&id[0],&id[A],-1);
	for(register unsigned i=0;i<vec.size();i++) id[vec[i]]=i;
	for(register int i=1;i<=n;i++) {
		for(register int j=1;j*j<=a[i];j++) {
			if(a[i]%j!=0) continue;
			if(id[j]!=-1) set[id[j]].insert(i);
			if(id[a[i]/j]!=-1) set[id[a[i]/j]].insert(i);
		}
	}
	for(register int i=0;i<m;i++) {
		const int &opt=o[i].type,&l=o[i].l,&r=o[i].r;
		if(opt==1) {
			const int &v=o[i].v;
			if(v==1) continue;
			const std::set<int>::iterator begin=set[id[v]].lower_bound(l);
			const std::set<int>::iterator end=set[id[v]].upper_bound(r);
			for(register std::set<int>::iterator i=begin;i!=end;) {
				if(a[*i]%v!=0) {
					set[id[v]].erase(i++);
					continue;
				}
				t.modify(*i,a[*i]/v-a[*i]);
				a[*i]/=v;
				if(a[*i]%v!=0) {
					set[id[v]].erase(i++);
					continue;
				}
				++i;
			}
		}
		if(opt==2) {
			printf("%lld
",t.query(l,r));
		}
	}
	return 0;
}

免责声明:文章转载自《[洛谷P3987]我永远喜欢珂朵莉~》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[CF115E]Linear Kingdom Races[POI2012]Squarks下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

bzoj3531

题解: 这一道题目和模板的差别在于这一刀题目还有一个信仰 如果没有信仰,那么就是模板 然后考虑对于每一个信仰,我们都建立一颗线段树 注意要动态开点 所以要数组多开大一些 代码: #include<bits/stdc++.h> using namespacestd; const int N=200005; intn,m,cnt,tot,al,ro...

LintCode-53.翻转字符串

翻转字符串 给定一个字符串,逐个翻转字符串中的每个单词。 说明 单词的构成:无空格字母构成一个单词 输入字符串是否包括前导或者尾随空格?可以包括,但是反转后的字符不能包括 如何处理两个单词间的多个空格?在反转字符串中间空格减少到只含一个 标签 字符串处理 code class Solution { public: /** * @pa...

基于FPGA的简易数字时钟

基于FPGA的可显示数字时钟,设计思路为自底向上,包含三个子模块:时钟模块,进制转换模块。led显示模块。所用到的FPGA晶振频率为50Mhz,首先利用它得到1hz的时钟然后然后得到时钟模块。把时钟模块输出的时、分、秒输入到进制转换模块后得到十进制的值再输入到led显示模块,该project已经在FPGA开发板上亲測可用。 下图为模块示意图(实际pro...

leetcode—Palindrome 解题报告

1.题目描述 Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s =...

STM32CubeIDE+FreeRTOS消息队列实验

新建工程RTOS_Message,配置如下: Ctrl + S生成代码 修改代码, 1,在main.h中添加 //添加include/*Private includes ----------------------------------------------------------*/ /*USER CODE BEGIN Includes */#...

Leetcode 881 救生艇 双指针

JAVA: public final int numRescueBoats(int[] people, intlimit) { if (people == null || people.length == 0) return 0; Arrays.sort(people); int len = peo...