Day8

T1:

题目：

给你一个数组，找出最长的一个区间，使得该区间中的不同数的个数不超过k.

思路：

使用双指针。当区间内的不同数的个数不超过k时，移动右指针，扩大区间。超过时，移动左指针，缩小区间。长区间的不同数的数量一定不少于短区间的不同数的数量。

代码（我用queue维护区间+桶数组维护不同数的数量）

//扫一边过去，队列。
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[500005];
int t[1000005];
int ans;
int cnt;
int ansl,ansr;
queue<int>q;
int main() {
	scanf("%d%d",&n,&k);
	for(int i = 1;i <= n;i ++)
		scanf("%d",a+i);
	for(int i = 1;i <= n;i ++) {
		int x = a[i];
		if(t[x] == 0) {
			t[x] ++;
			cnt ++;
			q.push(x);
		} else {
			t[x] ++;
			q.push(x);
		}
		while(cnt > k) {
			int y = q.front();
			t[y] --;
            q.pop();
			if(t[y] == 0) cnt --;
		}
		if((int)q.size() > ans) {
			ansl = i-(int)q.size()+1;
			ansr = i;
			ans = (int)q.size();
		}
	}
	printf("%d %d",ansl,ansr);
	return 0;
} 

T2:

题目：

给定一个数组，执行两种操作：

• 1 l r 对于任意的l<=i<=r,将a[i]修改为a[i]的数位之和。

• 2 x 输出a[x]

思路：

观察发现每个数最多变化两次就会变为个位数，不再变化。所以我们可以用set来维护还没有变为个位数的点的下标，进行1号查询的时候就把l~r之间还没有到头的（在set中的）给做一次数位求和操作。如果<10,那么就移出set，将a[i]的值替换一下。2号查询，直接输出a[i]即可。

复杂度大概为O(3n*q*log(n))

/*
数位之和，衰减的很快
可以求出每个数换为数位和之后的结果
变到个位数之后就不会在再变了
最多变两次 */
#include<bits/stdc++.h>
using namespace std;
int T;
int n,q;
int a[200005];
int op;
int l,r;
set<int>st;
void solve() {
	st.clear();
	scanf("%d%d",&n,&q);
	for(int i = 1;i <= n;i ++) {
		scanf("%d",a+i);
		if(a[i] >= 10) st.insert(i); 
	} 
	while(q --) {
		scanf("%d",&op);
		if(op == 1) {
			scanf("%d%d",&l,&r);
            auto it=st.lower_bound(l);
			while(it != st.end() && (*it) <= r){
                int x = a[*it];
                if(x >= 10) {
                    int x_ = x;
                    int sum = 0;
                    while(x_) {
                        sum += x_%10;
                        x_ /= 10;
                    }
                    x = sum;		
                }
                a[*it] = x;
                if(a[*it] < 10) it = st.erase(it);
                else ++it;
			}
		} else {
			int x;
			scanf("%d",&x);
			printf("%d\n",a[x]);
		}
	}
	
}
int main() {
	cin >> T;
	while(T --) solve();
	return 0;
}