题目：CF704A
题意：手机里n个应用，q次操作，每个操作三种类型。
type1:将一条x应用的消息加入，标为未读
type2:将x应用的消息全部读一下（包括未读和已读）
type3:将所有操作类型为1加入的消息读一下（包括未读和已读）
解答：定义一个数组，每次是第一种情况的时候将该类型加入数组。记录每个应用的未读消息数目以便查找。记录每一个应用的未读消息到了数组的哪个位置
解答过程：1、wa:处理第二种情况时没有把该应用的未读消息清空，导致多减了
2、wa:没有考虑第三种情况之前已经读过的不能再读了
3、tle:第三种情况的时候每次都从头搜，复杂度太高。
优化：每次是第三种情况处理完，标记它处理到哪个位置了。因为第三种情况下每次都是从头开始找
反思：思考问题应该更加注意细节、分析每次操作的特点
#include<iostream> #include<cstdio> using namespace std; const int MAXN = 300000+30; int num[MAXN],endp[MAXN],arr[MAXN];//num表示每个数当前未读的有几个，endup表示每个数通过第二种方式删到了数组的第几位，arr表示当前数组 int main() { int n,q,x,t; scanf("%d%d",&n,&q); int pos = 1,ans = 0,fr = 0;//pos表示当前数组的长度，fr表示通过第三种方式删到数组的第几位了 for(int i = 0;i < q;i++) { scanf("%d%d",&t,&x); if(t == 1) { ans++; num[x]++; arr[pos++] = x; } else if(t == 2) { endp[x] = pos; ans -= num[x]; num[x] = 0;/// } else if(t == 3) { if(x > fr) { for(int j = fr+1;j <= x;j++) { if(j >= endp[arr[j]])//如果arr[j]没删到j { ans--; num[arr[j]]--; } } fr = x; } } printf("%d\n",ans); } return 0; }